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


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}

Questions and Answers

You need to be logged in to be able to post here.