Both works refer to deciding properties of distributions that are represented by (succinct) sampling devices (i.e., circuits); that is, we refer to the distribution induced by the output of the given circuit, when feeding it with random inputs. This (``non-black-box'') model is fundamentally different from the (``black box'') model (studied in Property Testing) where one is only given samples from the distribution.
The first work studies the complexity of approximating the min-entropy of a sampleable distribution, where the analogous problem of approximating the shannon entropy was studied in the past. The second work studies the complexity of exactly computing some parameters of a sampleable distribution, where prior works have refered to approxmating such parameters.
Both work establish cmpleteness with respect to natural complxity classes, alas ones that are not best known. (Of course, this is not the author's fault -- it is the fault of reality...) The first work refers to SBP the class of promise problems defined by an NP-relation $R$ and a polynomial-time computible function $F$, where the task is to distinguish $x$'s for which $|R(x)| \geq F(x)$ from $x$'s for which $|R(x)| < F(x)/2$. The second work refers to C=P the class of problems defined by an NP-relation $R$ such that $R(x) \subseteq\{0,1\}^{\ell(|x|)}$ where the task is to distinguish $x$'s for which $|R(x)| = 2^{\ell(|x|)-1}$ from $x$'s for which $|R(x)| \neq 2^{\ell(|x|)-1}$; that is, these are exact counting problems rather than threshold counting problems (where one would used $\geq$ and $<$ respectively).
1. The Complexity of Estimating Min-Entropy
Goldreich, Sahai, and Vadhan (CRYPTO 1999) proved that the promise problem for estimating the Shannon entropy of a distribution sampled by a given circuit is NISZK-complete. We consider the analogous problem for estimating the min-entropy and prove that it is SBP-complete, even when restricted to 3-local samplers. For logarithmic-space samplers, we observe that this problem is NP-complete by a result of Lyngs{\o} and Pedersen on hidden Markov models (JCSS 2002).
2. The Complexity of Deciding Statistical Properties of Samplable Distributions
We consider the problems of deciding whether the joint distribution sampled by a given circuit satisfies 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 introduce a bounded-error version of C=P, which we call BC=P, and we investigate its structural properties.