Complexity theory typically studies the complexity of computing a function h(x) : {0, 1}m → {0,1}n of a given input x. We advocate the study of the complexity of generating the distribution h(x) for uniform x, given random bits. Our main results are: (1) Any function f : {0, 1}ℓ → {0,1}n such that (i) each output bit fi depends on o(log n) input bits, and (ii) ℓ ≤ log2 (αnn) + n0.99, has output distribution f(U) at statistical distance ≥ 1 - 1/n0.49 from the uniform distribution over n-bit strings of hamming weight αn. We also prove lower bounds for generating (X, b(X)) for boolean b, and in the case in which each bit fi is a small-depth decision tree. These lower bounds seem to be the first of their kind; the proofs use anti-concentration results for the sum of random variables. (2) Lower bounds for generating distributions imply succinct data structures lower bounds. As a corollary of (1), we obtain the first lower bound for the membership problem of representing a set S ⊆ [n] of size αn, in the case where 1/α is a power of 2: If queries "i ∈ S?" are answered by non-adaptively probing o(log n) bits, then the representation uses ≥ log2 (αn3) + Ω(log n) bits. (3) Upper bounds complementing the bounds in (1) for various settings of parameters. (4) Uniform randomized AC0 circuits of poly(n) size and depth d = O(1) with error ϵ can be simulated by uniform randomized AC0 circuits of poly(n) size and depth d + 1 with error ϵ + o(1) using ≤ (log n)O(log log n) random bits. Previous derandomizations [Ajtai and Wigderson '85; Nisan '91] increase the depth by a constant factor, or else have poor seed length.