×

Extractors for circuit sources. (English) Zbl 1301.68195

Summary: 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 \(\leq 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 L. Trevisan and S. Vadhan [“Extracting randomness from samplable distributions”, in: Proceedings of the 41st annual symposium on foundations of computer science. Los Alamitos, CA: IEEE Computer Society. 32–42 (2000; doi:10.1109/SFCS.2000.892063)] 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, No. 1, 191–218 (2012; Zbl 1255.68077); S. Lovett and E. Viola, Comput. Complexity 21, No. 2, 245–266 (2012; Zbl 1282.68125)]. 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 A. Rao [“Extractors for low-weight affine sources”, in: Proceedings of the 24th annual IEEE conference on computational complexity. Los Alamitos, CA: IEEE Computer Society. 95–101 (2009; doi:10.1109/CCC.2009.36)]. 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, A. De and T. Watson [Lect. Notes Comput. Sci. 6845, 483–494 (2011; Zbl 1343.94028)] obtain a result similar to (1) in the special case \(d = o(\lg n)\).

MSC:

68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI