2026-07-26T17:47:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6655 2024-03-06T10:38:36Z ddc:004 open_access

On Polynomial Approximations to AC^0 Harsha, Prahladh Srinivasan, Srikanth Constant-depth Boolean circuits Polynomials over reals pseudo-random generators k-wise independence We make progress on some questions related to polynomial approximations of AC^0. It is known, from the works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. 6th CCC 1991), that any AC^0 circuit of size s and depth d has an epsilon-error probabilistic polynomial over the reals of degree (log (s/epsilon))^{O(d)}. We improve this upper bound to (log s)^{O(d)}* log(1/epsilon), which is much better for small values of epsilon. We give an application of this result by using it to resolve a question posed by Tal (ECCC 2014): we show that (log s)^{O(d)}* log(1/epsilon)-wise independence fools AC^0, improving on Tal's strengthening of Braverman's theorem (J. ACM 2010) that (log (s/epsilon))^{O(d)}-wise independence fools AC^0. Up to the constant implicit in the O(d), our result is tight. As far as we know, this is the first PRG construction for AC^0 that achieves optimal dependence on the error epsilon. We also prove lower bounds on the best polynomial approximations to AC^0. We show that any polynomial approximating the OR function on n bits to a small constant error must have degree at least ~Omega(sqrt{log n}). This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prahladh Harsha and Srikanth Srinivasan 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.32 urn:nbn:de:0030-drops-66550 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.32 eng https://creativecommons.org/licenses/by/3.0/legalcode