Extractors for Circuit Sources
Emanuele Viola · SIAM Journal on Computing · 2011
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 $\mathrm{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 min-entropy $k$ that are generated by $\mathrm{poly}(n)$-size $\mathrm{AC}^0$ circuits, for any $\gamma > 0$. As our starting point, we revisit the connection by Trevisan and Vadhan [IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2000, pp. 32--42] 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 [E. Viola, SIAM J. Comput., 41 (2012), pp. 191--218; S. Lovett and E. Viola, Comput. Complexity, 21 (2012), pp. 245--256]. 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 [IEEE Conference on Computational Complexity, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 95--101]. Along the way, we exhibit an explicit boolean function $b : \{0, 1\}^n \to \{0, 1\}$ such that $\mathrm{poly}(n)$-size $\mathrm{AC}^0$ circuits cannot generate the distribution $(Y,b(Y))$, solving a problem about the complexity of distributions. Independently, De and Watson [ACM Trans. Comput. Theory, 4 (2012), 3] obtain a result similar to (1) in the special case $d = o(\lg n)$.