FOCS 2011
TechTalks from event: FOCS 2011
We will be uploading the videos for FOCS 2011 during the week of Nov 28th 2011. If you find any discrepancy, please let us know by clicking on report error link on talk page. If you did not permit the video to be published and by mistake we have published your talk, please notify us immediately at support AT weyond.com
3B

Extractors for circuit sourcesWe obtain the first deterministic extractors for sources generated (or sampled) by small circuits of bounded depth. Our main results are: (1) We extract $k (k/nd)^{O(1)}$ bits with exponentially small error from $n$bit sources of minentropy $k$ that are generated by functions $f : \{0,1\}^\ell \to \{0,1\}^n$ where each output bit depends on $\le d$ input bits. In particular, we extract from $NC^0$ sources, corresponding to $d = O(1)$. (2) We extract $k (k/n^{1+\gamma})^{O(1)}$ bits with superpolynomially small error from $n$bit sources of minentropy $k$ that are generated by $\poly(n)$size $AC^0$ circuits, for any $\gamma > 0$. As our starting point, we revisit the connection by Trevisan and Vadhan (FOCS 2000) between circuit lower bounds and extractors for sources generated by circuits. We note that such extractors (with very weak parameters) are equivalent to lower bounds for generating distributions (FOCS 2010; with Lovett, CCC 2011). Building on those bounds, we prove that the sources in (1) and (2) are (close to) a convex combination of highentropy ``bitblock'' sources. Introduced here, such sources are a special case of affine ones. As extractors for (1) and (2) one can use the extractor for lowweight affine sources by Rao (CCC 2009). Along the way, we exhibit an explicit boolean function $b : \{0,1\}^n \to \{0,1\}$ such that $\poly(n)$size $AC^0$ circuits cannot generate the distribution $(x,b(x))$, solving a problem about the complexity of distributions. Independently, De and Watson (ECCC TR11037) obtain a result similar to (1) in the special case $d = o(\lg n)$.

Randomness buys depth for approximate countingWe show that the promise problem of distinguishing $n$bit strings of hamming weights $1/2 +/ \Omega(1/\log^{d1} n)$ can be solved by explicit, randomized (unboundedfanin) $\poly(n)$size depth$d$ circuits with error $\le 1/3$, but cannot be solved by deterministic $\poly(n)$size depth$(d+1)$ circuits, for every $d \ge 2$; and the depth of both is tight. Previous results bounded the depth to within at least an additive 2. Our sharper bounds match Ajtai's simulation of randomized depth$d$ circuits by deterministic depth$(d+2)$ circuits (Ann.~Pure Appl.~Logic; '83), and provide an example where randomization (provably) buys resources. \bigskip \emph{Techniques:} To rule out deterministic circuits we combine the switching lemma with an earlier depth$3$ lower bound by the author (Comp.~Complexity 2009). To exhibit randomized circuits we combine recent analyses by Amano (ICALP '09) and Brody and Verbin (FOCS '10) with derandomization. To make these circuits explicit  which we find important for the main message of this paper  we construct a new pseudorandom generator for certain combinatorial rectangle tests. Based on expander walks, the generator for example fools tests $A_1 \times A_2 \times \ldots \times A_{\lg n}$ for $A_i \subseteq [n], A_i = n/2$ with error $1/n$ and seed length $O(\lg n)$, improving on the seed length $\Omega(\lg n \lg \lg n)$ of previous constructions.

Pseudorandomness for readonce formulasWe give an explicit construction of a pseudorandom generator for readonce formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fanin at most $d = O(n/\log n)$, the pseudorandom generator uses $(1  \Omega(1))n$ bits of randomness and produces an output that looks $2^{\Omega(n)}$pseudorandom to all such formulas. Our analysis is based on the following lemma. Let $pr = Mz + e$, where $M$ is the paritycheck matrix of a sufficiently good binary errorcorrecting code of constant rate, $z$ is a random string, $e$ is a smallbias distribution, and all operations are modulo 2. Then for every pair of functions $f, g\colon \B^{n/2} \to \B$ and every equipartition $(I,J)$ of $[n]$, the distribution $pr$ is pseudorandom for the pair $(f(x_I), g(x_J))$, where $x_I$ and $x_J$ denote the restriction of $x$ to the coordinates in $I$ and $J$, respectively.

Dispersers for affine sources with subpolynomial entropyWe construct an explicit disperser for affine sources over $\F_2^n$ with entropy $k=2^{\log^{0.9} n}=n^{o(1)}$. This is a polynomial time computable function $\Disp:\F_2^n \ar \B$ such that for every affine space $V$ of $\F_2^n$ that has dimension at least $k$, $\Disp(V)=\set{0,1}$. This improves the best previous construction of \cite{BK} that achieved $k = \Omega(n^{4/5})$. Our technique follows a high level approach that was developed in \cite{BKSSW,BRSW} in the context of dispersers for two independent general sources. The main steps are: \begin{itemize} \item Adjust the high level approach to make it suitable for affine sources. \item Implement a ``challengeresponse game'' for affine sources (in the spirit of \cite{BKSSW,BRSW} that introduced such games for two independent general sources). \item In order to implement the game, we construct extractors for affine blockwise sources. For this we use ideas and components from \cite{Rao09}. \item Combining the three items above, we obtain dispersers for affine sources with entropy that larger than $\sqrt{n}$, and we use a recursive winwin analysis in the spirit of \cite{RSW} to get affine dispersers with entropy less than $\sqrt{n}$. \end{itemize} 53.

A Small PRG for Polynomial Threshold Functions of GaussiansWe develop a new pseudorandom generator for fooling arbitrary degree$d$ polynomial threshold functions with respect to the Gaussian distribution. Our generator fools such functions to within $\epsilon$ with a generator of seed length $\log(n)2^{O(d)}\epsilon^{4c}$, where $c$ is an arbitrarily small positive constant.