The Complexity of Distributions
Emanuele Viola · SIAM Journal on Computing · 2012
Complexity theory typically studies the complexity of computing a function $h(x) : \{0, 1\}^m \to \{0, 1\}^n$ of a given input x. A few works have suggested studying the complexity of generating—or sampling—the distribution $h(x)$ for uniform x, given random bits. We further advocate this study, with a new emphasis on lower bounds for restricted computational models. Our main results are the following: (1) Any function $f : \{0, 1\}^\ell \to \{0, 1\}^n$ such that (i) each output bit $f_i$ depends on $o(\log n)$ input bits, and (ii) $\ell \le \log_2 \binom{n}{\alpha n} + n^{0.99}$ has output distribution $f(U)$ at statistical distance $\ge 1 - 1/n^{0.49}$ from the uniform distribution over n-bit strings of hamming weight $\alpha n$. We also prove lower bounds for generating $(X,b(X))$ for Boolean b, and in the case in which each bit $f_i$ is a small-depth decision tree. These lower bounds seem to be the first of their kind; the proofs use anticoncentration results for the sum of random variables. (2) Lower bounds for succinct data structures. As a corollary of (1), we obtain the first lower bound for the membership problem of representing a set $S \subseteq [n]$ of size $\alpha n$, in the case where $1/\alpha$ is a power of 2: If queries “$i \in S$?” are answered by nonadaptively probing $o(\log n)$ bits, then the representation uses $\ge \log_2 \binom{n}{\alpha n} + \Omega(\log n)$ bits. (3) Upper bounds complementing the bounds in (1) for various settings of parameters. (4) Uniform randomized $\mathrm{AC}^0$ circuits of $\mathrm{poly}(n)$ size and depth $d = O(1)$ with error $\epsilon$ can be simulated by uniform randomized $\mathrm{AC}^0$ circuits of $\mathrm{poly}(n)$ size and depth $d+1$ with error $\epsilon + o(1)$ using $\le (\log n)^{O( \log \log n)}$ random bits. Previous derandomizations [M. Ajtai and A. Wigderson, Adv. Comput. Res., 5 (1989), pp. 199–223], [N. Nisan, Combinatorica, 11 (1991), pp. 63–70] increase the depth by a constant factor, or else have poor seed length.