Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

## Description

Complexity theory typically studies the complexity of computing a function \$h(x) : {0,1}^m o {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:

egin{enumerate} item Any function \$f : {0,1}^ell o {0,1}^n\$ such that (i) each output bit \$f_i\$ depends on \$o(log n)\$ input bits, and (ii) \$ell le log_2 inom{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 anti-concentration results for the sum of random variables.

item 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 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 non-adaptively probing \$o(log n)\$ bits, then the representation uses \$ge log_2 inom{n}{alpha n} + Omega(log n)\$ bits.

item Upper bounds complementing the bounds in (1) for various settings of parameters.

item Uniform randomized AC\$^0\$ circuits of \$poly(n)\$ size and depth \$d = O(1)\$ with error \$e\$ can be simulated by uniform randomized AC\$^0\$ circuits of \$poly(n)\$ size and depth \$d+1\$ with error \$e + o(1)\$ using \$le (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. end{enumerate}