
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document 
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document 
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Description
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 smalldepth decision tree.
These lower bounds seem to be the first of their kind; the proofs use anticoncentration 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 nonadaptively 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}