Document Open Access Logo

Parity Helps to Compute Majority

Authors Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan

PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.23.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Igor Carboni Oliveira
  • Department of Computer Science, University of Oxford, UK
Rahul Santhanam
  • Department of Computer Science, University of Oxford, UK
Srikanth Srinivasan
  • Department of Mathematics, IIT Bombay, India

Funding

This work was supported in part by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2014)/ERC Grant Agreement no. 615075.

Acknowledgements

This paper is the result of a collaboration that happened at the Simons Institute program on Lower Bounds in Computational Complexity, where all three authors were long-term visitors. We are grateful to the Simons Institute for their support.

Cite As Get BibTex

Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity Helps to Compute Majority. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.23

Abstract

We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC^0[oplus] circuits. Razborov [Alexander A. Razborov, 1987] and Smolensky [Roman Smolensky, 1987; Roman Smolensky, 1993] showed that Majority requires depth-d AC^0[oplus] circuits of size 2^{Omega(n^{1/2(d-1)})}. By using a divide-and-conquer approach, it is easy to show that Majority can be computed with depth-d AC^0[oplus] circuits of size 2^{O~(n^{1/(d-1)})}. This gap between upper and lower bounds has stood for nearly three decades.
Somewhat surprisingly, we show that neither the upper bound nor the lower bound above is tight for large d. We show for d >= 5 that any symmetric function can be computed with depth-d AC^0[oplus] circuits of size exp(O~(n^{2/3 * 1/(d-4)})). Our upper bound extends to threshold functions (with a constant additive loss in the denominator of the double exponent). We improve the Razborov-Smolensky lower bound to show that for d >= 3 Majority requires depth-d AC^0[oplus] circuits of size 2^{Omega(n^{1/(2d-4)})}. For depths d <= 4, we are able to refine our techniques to get almost-optimal bounds: the depth-3 AC^0[oplus] circuit size of Majority is 2^{Theta~(n^{1/2})}, while its depth-4 AC^0[oplus] circuit size is 2^{Theta~(n^{1/4})}.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Computational Complexity
  • Boolean Circuits
  • Lower Bounds
  • Parity
  • Majority

Metrics

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

References

  1. Miklós Ajtai. ∑₁¹-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. Google Scholar
  2. Miklós Ajtai and Michael Ben-Or. A Theorem on Probabilistic Constant Depth Computations. In Symposium on Theory of Computing (STOC), pages 471-474, 1984. Google Scholar
  3. Josh Alman and Ryan Williams. Probabilistic Polynomials and Hamming Nearest Neighbors. In Symposium on Foundations of Computer Science (FOCS), pages 136-150, 2015. Google Scholar
  4. Kazuyuki Amano. Bounds on the Size of Small Depth Circuits for Approximating Majority. In International Colloquium on Automata, Languages and Programming (ICALP), pages 59-70, 2009. Google Scholar
  5. James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich. The Expressive Power of Voting Polynomials. Combinatorica, 14(2):135-148, 1994. Google Scholar
  6. David A. Mix Barrington, Richard Beigel, and Steven Rudich. Representing Boolean Functions as Polynomials Modulo Composite Numbers. Computational Complexity, 4:367-382, 1994. URL: https://doi.org/10.1007/BF01263424.
  7. Paul Beame. A switching lemma primer. Technical report, UW-CSE-95-07-01, 1994. Google Scholar
  8. Ravi B. Boppana. Threshold Functions and Bounded Depth Monotone Circuits. In Symposium on Theory of Computing (STOC), pages 475-479, 1984. URL: https://doi.org/10.1145/800057.808716.
  9. Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. Pseudorandom Generators from the Second Fourier Level and Applications to AC⁰ with Parity Gates. In Innovations in Theoretical Computer Science Conference (ITCS), pages 22:1-22:15, 2019. Google Scholar
  10. Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan. Near-optimal small-depth lower bounds for small distance connectivity. In Symposium on Theory of Computing (STOC), pages 612-625, 2016. Google Scholar
  11. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  12. Frederic Green. A complex-number Fourier technique for lower bounds on the Mod-m degree. Computational Complexity, 9(1):16-38, 2000. Google Scholar
  13. Kristoffer Hansen and Vladimir Podolskii. Exact Threshold Circuits. In Conference on Computational Complexity (CCC), pages 270-279, 2010. Google Scholar
  14. Johan Håstad. Almost Optimal Lower Bounds for Small Depth Circuits. In Symposium on Theory of Computing (STOC), pages 6-20, 1986. Google Scholar
  15. Peter Keevash and Benny Sudakov. Set Systems with Restricted Cross-Intersections and the Minimum Rank of Inclusion Matrices. SIAM J. Discrete Math., 18(4):713-727, 2005. Google Scholar
  16. Swastik Kopparty. AC⁰ lower bounds and pseudorandomness, 2013. Lecture notes on `Topics in Complexity Theory and Pseudorandomness'. Can be found at: URL: http://sites.math.rutgers.edu/~sk1233/courses/topics-S13/lec4.pdf.
  17. Swastik Kopparty and Srikanth Srinivasan. Certifying Polynomials for AC⁰[⊕] Circuits, with Applications to Lower Bounds and Circuit Compression. Theory of Computing, 14(1):1-24, 2018. Google Scholar
  18. Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. The Coin Problem in Constant Depth: Sample Complexity and Parity gates. Electronic Colloquium on Computational Complexity (ECCC), 157, 2018. Google Scholar
  19. Alexis Maciel and Denis Thérien. Threshold Circuits of Small Majority-Depth. Inf. Comput., 146(1):55-83, 1998. URL: https://doi.org/10.1006/inco.1998.2732.
  20. Zipei Nie and Anthony Y Wang. Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry. Journal of Combinatorial Theory, Series A, 134:196-220, 2015. Google Scholar
  21. Ryan O'Donnell and Karl Wimmer. Approximation by DNF: Examples and Counterexamples. In International Colloquium on Automata, Languages and Programming (ICALP), pages 195-206, 2007. Google Scholar
  22. Ramamohan Paturi, Michael E. Saks, and Francis Zane. Exponential lower bounds for depth three Boolean circuits. Computational Complexity, 9(1):1-15, 2000. URL: https://doi.org/10.1007/PL00001598.
  23. Alexander A. Razborov. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematicheskie Zametki, 41(4):598-607, 1987. Google Scholar
  24. Benjamin Rossman and Srikanth Srinivasan. Separation of AC⁰[⊕] Formulas and Circuits. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 50:1-50:13, 2017. Google Scholar
  25. Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Symposium on Theory of Computing (STOC), pages 77-82, 1987. Google Scholar
  26. Roman Smolensky. On Representations by Low-Degree Polynomials. In Symposium on Foundations of Computer Science (FOCS), pages 130-138, 1993. Google Scholar
  27. Mario Szegedy. Algebraic Methods in Lower Bounds for Computational Models. PhD thesis, University of Chicago, 1989. Google Scholar
  28. Leslie G. Valiant. Short Monotone Formulae for the Majority Function. J. Algorithms, 5(3):363-366, 1984. Google Scholar
  29. Victor K. Wei. Generalized Hamming weights for linear codes. IEEE Transactions on Information Theory, 37(5):1412-1418, 1991. 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