Document Open Access Logo

Smaller ACC0 Circuits for Symmetric Functions

Authors Brynmor Chapman, R. Ryan Williams

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.38.pdf
  • Filesize: 0.74 MB
  • 19 pages

Document Identifiers

Author Details

Brynmor Chapman
  • Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, USA
R. Ryan Williams
  • Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, USA

Funding

Supported by NSF CCF-1909429, NSF CCF-1741615, and a Frank Quick Faculty Research Innovation Fellowship.

Acknowledgements

We thank Arkadev Chattopadhyay and Kristoffer Arnsfelt Hansen for useful pointers and discussion.

Cite AsGet BibTex

Brynmor Chapman and R. Ryan Williams. Smaller ACC0 Circuits for Symmetric Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.38

Abstract

What is the power of constant-depth circuits with MOD_m gates, that can count modulo m? Can they efficiently compute MAJORITY and other symmetric functions? When m is a constant prime power, the answer is well understood. In this regime, Razborov and Smolensky proved in the 1980s that MAJORITY and MOD_m require super-polynomial-size MOD_q circuits, where q is any prime power not dividing m. However, relatively little is known about the power of MOD_m gates when m is not a prime power. For example, it is still open whether every problem decidable in exponential time can be computed by depth-3 circuits of polynomial-size and only MOD_6 gates. In this paper, we shed some light on the difficulty of proving lower bounds for MOD_m circuits, by giving new upper bounds. We show how to construct MOD_m circuits computing symmetric functions with non-prime power m, with size-depth tradeoffs that beat the longstanding lower bounds for AC^0[m] circuits when m is a prime power. Furthermore, we observe that our size-depth tradeoff circuits have essentially optimal dependence on m and d in the exponent, under a natural circuit complexity hypothesis. For example, we show that for every ε > 0, every symmetric function can be computed using MOD_m circuits of depth 3 and 2^{n^ε} size, for a constant m depending only on ε > 0. In other words, depth-3 CC^0 circuits can compute any symmetric function in subexponential size. This demonstrates a significant difference in the power of depth-3 CC^0 circuits, compared to other models: for certain symmetric functions, depth-3 AC^0 circuits require 2^{Ω(√n)} size [Håstad 1986], and depth-3 AC^0[p^k] circuits (for fixed prime power p^k) require 2^{Ω(n^{1/6})} size [Smolensky 1987]. Even for depth-2 MOD_p ∘ MOD_m circuits, 2^{Ω(n)} lower bounds were known [Barrington Straubing Thérien 1990].

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • ACC
  • CC
  • circuit complexity
  • symmetric functions
  • Chinese Remainder Theorem

Metrics

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

References

  1. Manindra Agrawal, Eric Allender, and Samir Datta. On TC^0, AC^0, and arithmetic circuits. J. Comput. Syst. Sci., 60(2):395-421, 2000. Google Scholar
  2. Eric Allender and Vivek Gore. A uniform circuit lower bound for the permanent. SIAM J. Comput., 23(5):1026-1049, 1994. URL: https://doi.org/10.1137/S0097539792233907.
  3. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. JACM, 57(3), 2010. Google Scholar
  4. Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, and V. Vinay. Time-space tradeoffs in the counting hierarchy. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pages 295-302. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/CCC.2001.933896.
  5. Kazuyuki Amano. Bounds on the size of small depth circuits for approximating majority. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, volume 5555 of Lecture Notes in Computer Science, pages 59-70. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_7.
  6. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. Google Scholar
  7. David Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC¹. Journal of Computer and System Sciences, 41, 1990. Google Scholar
  8. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. J. Comput. Syst. Sci., 38(1):150-164, 1989. See also STOC'86. Google Scholar
  9. David A. Mix Barrington, Richard Beigel, and Steven Rudich. Representing Boolean functions as polynomials modulo composite numbers. Comput. Complexity, 4:367-382, 1994. Google Scholar
  10. David A. Mix Barrington, Howard Straubing, and Denis Thérien. Non-uniform automata over groups. Inf. Comput., 89(2):109-132, 1990. Google Scholar
  11. David A. Mix Barrington and Denis Thérien. Finite monoids and the fine structure of NC1. J. ACM, 35(4):941-952, 1988. See also STOC'87. URL: https://doi.org/10.1145/48014.63138.
  12. Paul Beame, Erik Brisson, and Richard E. Ladner. The complexity of computing symmetric functions using threshold circuits. Theor. Comput. Sci., 100(1):253-265, 1992. URL: https://doi.org/10.1016/0304-3975(92)90372-M.
  13. Richard Beigel and Jun Tarui. On ACC. Computational Complexity, pages 350-366, 1994. Google Scholar
  14. Nayantara Bhatnagar, Parikshit Gopalan, and Richard J. Lipton. Symmetric polynomials over z_m and simultaneous communication protocols. J. Comput. Syst. Sci., 72(2):252-285, 2006. URL: https://doi.org/10.1016/j.jcss.2005.06.007.
  15. Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, and Denis Thérien. Lower bounds for circuits with MODm gates. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 709-718. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/FOCS.2006.46.
  16. Arkadev Chattopadhyay and Avi Wigderson. Linear systems over composite moduli. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pages 43-52. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.17.
  17. Lijie Chen, Xin Lyu, and R. Ryan Williams. Almost-everywhere circuit lower bounds from non-trivial derandomization. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1-12. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00009.
  18. Shiteng Chen and Periklis A. Papakonstantinou. Depth reduction for composites. SIAM J. Comput., 48(2):668-686, 2019. URL: https://doi.org/10.1137/17M1129672.
  19. Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan. Near-optimal small-depth lower bounds for small distance connectivity. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 612-625. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897534.
  20. Parikshit Gopalan. Computing with polynomials over composites. PhD thesis, Georgia Institute of Technology, 2006. Google Scholar
  21. Vince Grolmusz and Gábor Tardos. Lower bounds for (MOD_p-MOD_m) circuits. SIAM J. Comput., 29(4):1209-1222, 2000. Google Scholar
  22. Kristoffer Arnsfelt Hansen. On modular counting with polynomials. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), pages 202-212. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/CCC.2006.29.
  23. Kristoffer Arnsfelt Hansen and Michal Koucký. A new characterization of ACC0 and probabilistic CC0. Comput. Complex., 19(2):211-234, 2010. URL: https://doi.org/10.1007/s00037-010-0287-z.
  24. Kristoffer Arnsfelt Hansen and Vladimir V Podolskii. Exact threshold circuits. In CCC, pages 270-279, 2010. Google Scholar
  25. Johan Håstad. Almost optimal lower bounds for small depth circuits. In STOC, pages 6-20, 1986. Google Scholar
  26. Paweł M Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Complexity of modular circuits. arXiv preprint arXiv:2106.02947, 2021. Google Scholar
  27. Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer-Verlag, 2012. Google Scholar
  28. Edouard Lucas. Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques suivant un module premier. Bulletin de la Société Mathématique de France, 6:49-54, 1878. URL: https://doi.org/10.24033/bsmf.127.
  29. Cody D. Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma. SIAM J. Comput., 49(5), 2020. URL: https://doi.org/10.1137/18M1195887.
  30. V. Nepomnjascii. Rudimentary predicates and Turing calculations. Soviet Mathematics - Doklady, 11(6):1462-1465, 1970. Google Scholar
  31. Ryan O'Donnell and Karl Wimmer. Approximation by DNF: examples and counterexamples. In Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, volume 4596 of Lecture Notes in Computer Science, pages 195-206. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-73420-8_19.
  32. Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity helps to compute majority. In 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs, pages 23:1-23:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.23.
  33. Alexander A. Razborov. Lower bounds on the size of bounded-depth networks over the complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  34. Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In STOC, pages 77-82, 1987. Google Scholar
  35. Howard Straubing and Denis Thérien. A note on MODp - MODm circuits. Theory Comput. Syst., 39(5):699-706, 2006. Google Scholar
  36. Denis Thérien. Circuits constructed with MODq gates cannot compute AND in sublinear size. Comput. Complex., 4:383-388, 1994. URL: https://doi.org/10.1007/BF01263425.
  37. R. Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. Theory Comput., 14(1):1-25, 2018. Preliminary version in STOC'14. Google Scholar
  38. Ryan Williams. Nonuniform ACC circuit lower bounds. JACM, 61(1):2, 2014. See also CCC'11. Google Scholar
  39. Andrew Chi-Chih Yao. On ACC and threshold circuits. In FOCS, pages 619-627, 1990. 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