Document Open Access Logo

Tight Bounds on the Fourier Spectrum of AC0

Author Avishay Tal

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.15.pdf
  • Filesize: 0.72 MB
  • 31 pages

Document Identifiers

Author Details

Avishay Tal

Cite As Get BibTex

Avishay Tal. Tight Bounds on the Fourier Spectrum of AC0. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 15:1-15:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.15

Abstract

We show that AC^0 circuits on n variables with depth d and size m have at most 2^{-Omega(k/log^{d-1} m)} of their Fourier mass at level k or above. Our proof builds on a previous result by Hastad (SICOMP, 2014) who proved this bound for the special case k=n. Our result improves the seminal result of Linial, Mansour and Nisan (JACM, 1993) and is tight up to the constants hidden in the Omega notation. 

As an application, we improve Braverman's celebrated result (JACM, 2010). Braverman showed that any r(m,d,epsilon)-wise independent distribution epsilon-fools AC^0 circuits of size m and depth d, for r(m,d,epsilon) = O(log(m/epsilon))^{2d^2+7d+3}. Our improved bounds on the Fourier tails of AC^0 circuits allows us to improve this estimate to r(m,d,epsilon) = O(log(m/epsilon))^{3d+3}. In contrast, an example by Mansour (appearing in Luby and Velickovic's paper - Algorithmica, 1996) shows that there is a log^{d-1}(m)\log(1/epsilon)-wise independent distribution that does not epsilon-fool AC^0 circuits of size m and depth d. Hence, our result is tight up to the factor $3$ in the exponent.

Subject Classification

Keywords
  • bounded depth circuits
  • Fourier analysis
  • k-wise independence
  • Boolean circuits
  • switching lemma

Metrics

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

References

  1. S. Aaronson. BQP and the polynomial hierarchy. In STOC, pages 141-150, 2010. Google Scholar
  2. M. Ajtai. Σ₁¹-formulae on finite structures. Annals of Pure and Applied Logic, 24:1-48, 1983. Google Scholar
  3. N. Alon, O. Goldreich, J. Håstad, and R. Peralta. Simple construction of almost k-wise independent random variables. Random Structures and Algorithms, 3(3):289-304, 1992. Google Scholar
  4. L. M. J. Bazzi. Polylogarithmic independence can fool DNF formulas. SIAM J. Comput., 38(6):2220-2272, 2009. Google Scholar
  5. P. Beame. A switching lemma primer, 1994. Google Scholar
  6. R. B. Boppana. The average sensitivity of bounded-depth circuits. Inf. Process. Lett., 63(5):257-261, 1997. Google Scholar
  7. M. Braverman. Polylogarithmic independence fools AC⁰ circuits. J. ACM, 57(5):28:1-28:10, 2010. Google Scholar
  8. G. Cohen, A. Ganor, and R. Raz. Two sides of the coin problem. In APPROX-RANDOM, pages 618-629, 2014. Google Scholar
  9. A. De, O. Etesami, L. Trevisan, and M. Tulsiani. Improved pseudorandom generators for depth 2 circuits. In APPROX-RANDOM, pages 504-517, 2010. Google Scholar
  10. Y. Filmus. Smolensky’s lower bound. Unpublished Manuscript, 2010. Google Scholar
  11. M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, apr 1984. Google Scholar
  12. O. Goldreich and L. A. Levin. A hardcore predicate for all one-way functions. In STOC, pages 25-32, 1989. Google Scholar
  13. P. Harsha and S. Srinivasan. On polynomial approximations to AC^0. In RANDOM 2016, pages 32:1-32:14, 2016. Google Scholar
  14. J. Håstad. Almost optimal lower bounds for small depth circuits. In STOC, pages 6-20, 1986. URL: http://dx.doi.org/10.1145/12130.12132.
  15. J. Håstad. A slight sharpening of LMN. J. Comput. Syst. Sci., 63(3):498-508, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1803.
  16. J. Håstad. On the correlation of parity and small-depth circuits. SIAM J. Comput., 43(5):1699-1708, 2014. Google Scholar
  17. R. Impagliazzo and V. Kabanets. Fourier concentration from shrinkage. In CCC, pages 321-332, 2014. Google Scholar
  18. R. Impagliazzo, W. Matthews, and R. Paturi. A satisfiability algorithm for AC⁰. In SODA, pages 961-972, 2012. Google Scholar
  19. R. Kaas and J. M. Buhrman. Mean, median and mode in binomial distributions. Statistica Neerlandica, 34(1):13-18, 1980. Google Scholar
  20. J. Kahn, G. Kalai, and N. Linial. The influence of variables on Boolean functions. In FOCS, pages 68-80, 1988. Google Scholar
  21. E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. SIAM J. Comput., 22(6):1331-1348, 1993. Google Scholar
  22. N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform and learnability. J. ACM, 40(3):607-620, 1993. Google Scholar
  23. M. Luby and B. Velickovic. On deterministic approximation of DNF. Algorithmica, 16(4/5):415-433, 1996. Google Scholar
  24. O. Lupanov. Implementing the algebra of logic functions in terms of constant depth formulas in the basis &, ∨, ¬. Dokl. Akad. Nauk. SSSR, 136:1041-1042, 1961. In Russian. Google Scholar
  25. Y. Mansour. An O(n^log log n) learning algorithm for DNF under the uniform distribution. J. Comput. Syst. Sci., 50(3):543-550, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1043.
  26. J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. on Computing, 22(4):838-856, 1993. Google Scholar
  27. R. O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  28. R. O'Donnell and K. Wimmer. Approximation by DNF: examples and counterexamples. In ICALP, pages 195-206, 2007. Google Scholar
  29. A. A. Razborov. Bounded arithmetic and lower bounds in boolean complexity. In Feasible Mathematics II, volume 13 of Progress in Computer Science and Applied Logic, pages 344-386. Birkhäuser Boston, 1995. Google Scholar
  30. A. A. Razborov. A simple proof of Bazzi’s theorem. TOCT, 1(1), 2009. Google Scholar
  31. R. Shaltiel and E. Viola. Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122-3154, 2010. Google Scholar
  32. R. Smolensky. On representations by low-degree polynomials. In FOCS 1993, pages 130-138, 1993. Google Scholar
  33. A. Tal. Shrinkage of de Morgan formulae from quantum query complexity. In FOCS, pages 551-560, 2014. Google Scholar
  34. N. Thapen. Notes on switching lemmas. Unpublished Manuscript, 2009. URL: http://users.math.cas.cz/~thapen/switching.pdf.
  35. L. Trevisan and T. Xue. A derandomized switching lemma and an improved derandomization of AC0. In CCC, pages 242-247, 2013. Google Scholar
  36. A. C. Yao. Separating the polynomial hierarchy by oracles. In FOCS, pages 1-10, 1985. Google Scholar
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