Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-056 | 14th April 2011 14:53

Extractors for circuit sources


Authors: Emanuele Viola
Publication: 14th April 2011 14:54
Downloads: 3039


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)$.

ISSN 1433-8092 | Imprint