Document Open Access Logo

AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product

Authors Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.35.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Mahdi Cheraghchi
Elena Grigorescu
Brendan Juba
Karl Wimmer
Ning Xie

Cite AsGet BibTex

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.35

Abstract

AC^0 o MOD_2 circuits are AC^0 circuits augmented with a layer of parity gates just above the input layer. We study AC^0 o MOD2 circuit lower bounds for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have highlighted this problem as a frontier problem in circuit complexity that arose both as a first step towards solving natural special cases of the matrix rigidity problem and as a candidate for constructing pseudorandom generators of minimal complexity. We give the first superlinear lower bound for the Boolean Inner Product function against AC^0 o MOD2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an ~Omega(n^2) lower bound for the special case of depth-4 AC^0 o MOD_2. Our proof of the depth-4 lower bound employs a new "moment-matching" inequality for bounded, nonnegative integer-valued random variables that may be of independent interest: we prove an optimal bound on the maximum difference between two discrete distributions’ values at 0, given that their first d moments match.
Keywords
  • Boolean analysis
  • circuit complexity
  • lower bounds

Metrics

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

References

  1. A. Akavia, A. Bogdanov, S. Guo, A. Kamath, and A. Rosen. Candidate weak pseudorandom functions in AC⁰∘ MOD₂. In Proc. 5th ITCS, pages 251-260, 2014. Google Scholar
  2. T. Ando. Truncated moment problems for operators. Acta Sci. Math. (Szeged), 31:319-334, 1970. Google Scholar
  3. S. Chaudhuri and J. Radhakrishnan. Deterministic restrictions in circuit complexity. In Proc. 28th STOC, pages 30-36, 1996. Google Scholar
  4. G. Cohen and I. Shinkar. The complexity of DNF of parities. To appear in ITCS'16, 2016. Google Scholar
  5. R.E. Curto and L.A. Fialow. Recursiveness, positivity, and truncated moment problems. Houston J. Math., 17:603-635, 1991. Google Scholar
  6. A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, and G. Turán. Threshold circuits of bounded depth. JCSS, 46:129-154, 1993. Earlier version in FOCS'87. Google Scholar
  7. R. Impagliazzo, R. Shaltiel, and A. Wigderson. Reducing the seed length in the Nisan-Wigderson generator. Combinatorica, 26(6):647-681, 2006. Earlier version in FOCS'01. Google Scholar
  8. J.C. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. JCSS, 55(3):414-440, 1997. Google Scholar
  9. S. Jukna. On graph complexity. Combinatorics, Probability, and Computing, 15(6):855-876, 2006. Google Scholar
  10. A. Klivans and L. Fortnow. Efficient learning algorithms yield circuit lower bounds. JCSS, 75:27-36, 2009. Google Scholar
  11. A. Klivans, P. Kothari, and I.C. Oliveira. Constructing hard functions using learning algorithms. In Proc. 28th CCC, pages 86-97, 2013. Google Scholar
  12. A. Klivans and R. Meka. Moment-matching polynomials. Technical Report TR13-008, ECCC, 2013. Google Scholar
  13. S. Kopparty and S. Srinivasan. Certifying polynomials for AC⁰(⊕) circuits, with applications. In Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 36-47, 2012. Google Scholar
  14. N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. J. ACM, 40(3):607-620, 1993. Google Scholar
  15. N. Linial and N. Nisan. Approximate inclusion-exclusion. Combinatorica, 10(4):349-365, 1990. Google Scholar
  16. N. Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63-70, 1991. Google Scholar
  17. N. Nisan and M. Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. Earlier version in STOC'92. Google Scholar
  18. N. Nisan and A. Wigderson. Hardness versus randomness. JCSS, 49:149-167, 1994. Google Scholar
  19. R. Paturi. On the degree of polynomials that approximate symmetric Boolean functions. In Proc. 24th STOC, pages 468-474, 1992. Google Scholar
  20. S. Raskhodnikova, D. Ron, A. Shpilka, and A. Smith. Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM J. Comput., 39(3):813-842, 2009. Earlier version in FOCS'07. Google Scholar
  21. A.A. Razborov. Lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Math. Notes Acad. of Sci. USSR, 41(4):333-338, 1987. Google Scholar
  22. T. Rivlin. Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory. John Wiley &Sons, Inc., 1990. Google Scholar
  23. R. Servedio and E. Viola. On a special case of rigidity. Manuscript, 2012. Google Scholar
  24. R. Shaltiel and C. Umans. Simple extractors for all min-entropies and a new pseudo-random generator. J. ACM, 52(2):172-216, 2005. Earlier version appeared in FOCS'01. Google Scholar
  25. R. Shaltiel and E. Viola. Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122-3154, 2010. Google Scholar
  26. R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. 19th STOC, pages 77-82, 1987. Google Scholar
  27. C. Umans. Pseudo-random generators for all hardnesses. JCSS, 67(2):419-440, 2003. Earlier version appeared in CCC'02. Google Scholar
  28. L.G. Valiant. Graph-theoretic arguments in low-level complexity. In Proc. 6th MFCS, volume 53 of LNCS, pages 162-176. Springer, 1977. Google Scholar
  29. I. Volkovich. On learning, lower bounds and (un)keeping promises. In ICALP 2014, Part I, volume 8572 of LNCS, pages 1027-1038. Springer, 2014. 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 Imprint Privacy Contact