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


  • Extractors for circuit sources Authors: Emanuele Viola
    We 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 min-entropy $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 super-polynomially small error from $n$-bit sources of min-entropy $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 high-entropy ``bit-block'' sources. Introduced here, such sources are a special case of affine ones. As extractors for (1) and (2) one can use the extractor for low-weight 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 TR11-037) obtain a result similar to (1) in the special case $d = o(\lg n)$.
  • Randomness buys depth for approximate counting Authors: Emanuele Viola
    We show that the promise problem of distinguishing $n$-bit strings of hamming weights $1/2 +/- \Omega(1/\log^{d-1} n)$ can be solved by explicit, randomized (unbounded-fan-in) $\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 read-once formulas Authors: Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan
    We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fan-in 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 parity-check matrix of a sufficiently good binary error-correcting code of constant rate, $z$ is a random string, $e$ is a small-bias 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 sub-polynomial entropy Authors: Ronen Shaltiel
    We 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 ``challenge-response 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 block-wise 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 win-win 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 Gaussians Authors: Daniel M. Kane
    We develop a new pseudo-random 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^{-4-c}$, where $c$ is an arbitrarily small positive constant.