Theory of Computing
-------------------
Title     : The Complexity of Deciding Statistical Properties of Samplable Distributions
Authors   : Thomas Watson
Volume    : 11
Number    : 1
Pages     : 1-34
URL       : https://theoryofcomputing.org/articles/v011a001

Abstract
--------

We consider the problems of deciding whether the joint distribution
sampled by a given circuit has certain statistical properties such
as being i.i.d., being exchangeable, being pairwise independent,
having two coordinates with identical marginals, having two
uncorrelated coordinates, and many other variants. We give a proof
that simultaneously shows all these problems are C=P-complete, by
showing that the following promise problem (which is a restriction
of all the above problems) is C=P-complete: Given a circuit,
distinguish the case where the output distribution is uniform and
the case where every pair of coordinates is neither uncorrelated
nor identically distributed. This completeness result holds even
for samplers that are depth-3 circuits.

We also consider circuits that are d-local, in the sense that each
output bit depends on at most d input bits. We give linear-time
algorithms for deciding whether a 2-local sampler's joint
distribution is fully independent, and whether it is exchangeable.

We also show that for general circuits, certain approximation versions
of the problems of deciding full independence and exchangeability are
SZK-complete.

We also introduce a bounded-error version of C=P, which we call
BC=P, and we investigate its structural properties.

----

An extended abstract of this paper appeared in the Proceedings of
the 31st International Symposium on Theoretical Aspects of Computer
Science (STACS), 2014.