THE COMPLEXITY OF DISTRIBUTIONS
Complexity theory typically studies the complexity of computing a function h(x) : {0, 1}(m) -> {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}(l) -> {0, 1}(n) such that (i) each output bit f(i) depends on o(log n) input bits, and (ii) l  = 1 - 1/n(0.49) from the uniform distribution over n-bit strings of hamming weight an. 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 subset of [n] of size alpha n, in the case where 1/alpha is a power of 2: If queries "i is an element of S?" are answered by nonadaptively probing o(log n) bits, then the representation uses >= log(2) ((n) (alpha n)) + Omega(log n) bits. (3) Upper bounds complementing the bounds in (1) for various settings of parameters. (4) Uniform randomized AC(0) circuits of poly(n) size and depth d = O(1) with error epsilon can be simulated by uniform randomized AC(0) circuits of poly(n) size and depth d + 1 with error epsilon + o(1) using <= (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.
distribution lower bound decision tree succinct data structure sampling local pseudorandom generator