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