ECCC-Report TR11-056https://eccc.weizmann.ac.il/report/2011/056Comments and Revisions published for TR11-056en-usThu, 14 Apr 2011 14:54:04 +0300
Paper TR11-056
| Extractors for circuit sources |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2011/056We 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)$.
Thu, 14 Apr 2011 14:54:04 +0300https://eccc.weizmann.ac.il/report/2011/056