Document Open Access Logo

On Polynomial Approximations to AC^0

Authors Prahladh Harsha, Srikanth Srinivasan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.32.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Prahladh Harsha
Srikanth Srinivasan

Cite As Get BibTex

Prahladh Harsha and Srikanth Srinivasan. On Polynomial Approximations to AC^0. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.32

Abstract

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

Subject Classification

Keywords
  • Constant-depth Boolean circuits
  • Polynomials over reals
  • pseudo-random generators
  • k-wise independence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Miklós Ajtai and Michael Ben-Or. A theorem on probabilistic constant depth computations. In Proc. 16th ACM Symp. on Theory of Computing (STOC), pages 471-474, 1984. URL: http://dx.doi.org/10.1145/800057.808715.
  2. Richard Beigel, Nick Reingold, and Daniel A. Spielman. The perceptron strikes back. In Proc. 6th IEEE Conf. on Structure in Complexity Theory, pages 286-291, 1991. URL: http://dx.doi.org/10.1109/SCT.1991.160270.
  3. Mark Braverman. Polylogarithmic independence fools AC⁰ circuits. J. ACM, 57(5), 2010. (Preliminary version in 24th IEEE Conference on Computational Complexity, 2009). URL: http://dx.doi.org/10.1145/1754399.1754401.
  4. Kevin P. Costello, Terence Tao, and Van Vu. Random symmetric matrices are almost surely nonsingular. Duke Math. J., 135(2):395-413, 2006. http://arxiv.org/abs/math/0505156, URL: http://dx.doi.org/10.1215/S0012-7094-06-13527-5.
  5. Paul Erdős. On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc., 51(12):898-902, 1945. URL: http://dx.doi.org/10.1090/S0002-9904-1945-08454-7.
  6. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Silvio Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 143-170. JAI Press, Greenwich, Connecticut, 1989. (Preliminary version in 18th STOC 1986). URL: http://www.csc.kth.se/~johanh/largesmalldepth.pdf.
  7. Johan Håstad. On the correlation of parity and small-depth circuits. SIAM J. Comput., 43(5):1699-1708, 2014. URL: http://dx.doi.org/10.1137/120897432.
  8. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for AC⁰. In Proc. 23rd Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 961-972, 2012. URL: http://arxiv.org/abs/1107.3127.
  9. Swastik Kopparty and Srikanth Srinivasan. Certifying polynomials for AC⁰(parity) circuits, with applications. In Deepak D'Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan, editors, Proc. 32nd IARCS Annual Conf. on Foundations of Software Tech. and Theoretical Comp. Science (FSTTCS), volume 18 of LIPIcs, pages 36-47. Schloss Dagstuhl, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.36.
  10. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform, and learnability. J. ACM, 40(3):607-620, 1993. (Preliminary version in 30th FOCS, 1989). URL: http://dx.doi.org/10.1145/174130.174138.
  11. John Edensor Littlewood and A. Cyril Offord. On the number of real roots of a random algebraic equation. J. London Math. Soc., s1-13(4):288-295, 1938. URL: http://dx.doi.org/10.1112/jlms/s1-13.4.288.
  12. Michael Luby and Boban Velickovic. On deterministic approximation of DNF. Algorithmica, 16(4/5):415-433, 1996. (Preliminary version in 23rd STOC, 1991). URL: http://dx.doi.org/10.1007/BF01940873.
  13. Raghu Meka, Oanh Nguyen, and Van Vu. Anti-concentration for polynomials of independent random variables. arXiv 1507.00829, 2015. URL: https://arxiv.org/abs/1507.00829.
  14. Noam Nisan and Avi Wigderson. Hardness vs. Randomness. J. Comput. Syst. Sci., 49(2):149-167, October 1994. (Preliminary version in 29th FOCS, 1988). URL: http://dx.doi.org/10.1016/S0022-0000(05)80043-1.
  15. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: http://analysisofbooleanfunctions.org/, URL: http://dx.doi.org/10.1017/CBO9781139814782.
  16. Igor Carboni Oliveira and Rahul Santhanam. Majority is incompressible by AC⁰[p] circuits. In Proc. 30th Computational Complexity Conf., pages 124-157, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.124.
  17. Alexander A. Razborov. \foreignlanguagerussianНжние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения (Russian) [Lower bounds on the size of bounded depth circuits over a complete basis with logical addition]. Mathematicheskie Zametki, 41(4):598-607, 1987. (English translation in Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987). URL: http://mi.mathnet.ru/eng/mz4883, URL: http://dx.doi.org/10.1007/BF01137685.
  18. Alexander A. Razborov and Emanuele Viola. Real advantage. ACM T. Comput. Theory, 5(4):17, 2013. URL: http://dx.doi.org/10.1145/2540089.
  19. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proc. 19th ACM Symp. on Theory of Computing (STOC), pages 77-82, 1987. URL: http://dx.doi.org/10.1145/28395.28404.
  20. Avishay Tal. Tight bounds on the fourier spectrum of AC⁰. Technical Report TR14-174, Elect. Colloq. on Comput. Complexity (ECCC), 2014. Google Scholar
  21. Jun Tarui. Probablistic polynomials, AC⁰ functions, and the polynomial-time hierarchy. Theoret. Comput. Sci., 113(1):167-183, 1993. (Preliminary Version in 8th STACS, 1991). URL: http://dx.doi.org/10.1016/0304-3975(93)90214-E.
  22. Seinosuke Toda and Mitsunori Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Comput., 21(2):316-328, 1992. (Preliminary version in 6th Structure in Complexity Theory Conference, 1991). URL: http://dx.doi.org/10.1137/0221023.
  23. Luca Trevisan and Tongke Xue. A derandomized switching lemma and an improved derandomization of AC⁰. In Proc. 28th IEEE Conf. on Computational Complexity, pages 242-247, 2013. URL: http://dx.doi.org/10.1109/CCC.2013.32.
  24. Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. In Proc. 46th ACM Symp. on Theory of Computing (STOC), pages 194-202, 2014. http://arxiv.org/abs/1401.2444, URL: http://dx.doi.org/10.1145/2591796.2591858.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact