Document Open Access Logo

Symmetric Arithmetic Circuits

Authors Anuj Dawar , Gregory Wilsenach

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.36.pdf
  • Filesize: 0.57 MB
  • 18 pages

Document Identifiers

Author Details

Anuj Dawar
  • Department of Computer Science and Technology, University of Cambridge, UK
Gregory Wilsenach
  • Department of Computer Science and Technology, University of Cambridge, UK

Funding

Research funded in part by EPSRC grant EP/S03238X/1.

Cite As Get BibTex

Anuj Dawar and Gregory Wilsenach. Symmetric Arithmetic Circuits. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.36

Abstract

We introduce symmetric arithmetic circuits, i.e. arithmetic circuits with a natural symmetry restriction. In the context of circuits computing polynomials defined on a matrix of variables, such as the determinant or the permanent, the restriction amounts to requiring that the shape of the circuit is invariant under row and column permutations of the matrix. We establish unconditional, nearly exponential, lower bounds on the size of any symmetric circuit for computing the permanent over any field of characteristic other than 2. In contrast, we show that there are polynomial-size symmetric circuits for computing the determinant over fields of characteristic zero.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Algebraic complexity theory
Keywords
  • arithmetic circuits
  • symmetric arithmetic circuits
  • Boolean circuits
  • symmetric circuits
  • permanent
  • determinant
  • counting width
  • Weisfeiler-Leman dimension
  • Cai-Fürer-Immerman constructions

Metrics

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

Related Versions

References

  1. M. Ajtai. Recursive construction for 3-regular expanders. Combinatorica, 14:379-416, 1994. Google Scholar
  2. M. Anderson and A. Dawar. On symmetric circuits and fixed-point logics. Theory Comput. Syst., 60(3):521-551, 2017. Google Scholar
  3. M. Anderson, A. Dawar, and B. Holm. Solving linear programs without breaking abstractions. J. ACM, 62, 2015. Google Scholar
  4. V. Arvind, F. Fuhlbrück, J. Köbler, and O. Verbitsky. On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. In Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, pages 111-125, 2019. URL: https://doi.org/10.1007/978-3-030-25027-0_8.
  5. A. Atserias, A. Dawar, and J. Ochremiak. On the power of symmetric linear programs. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, pages 1-13, 2019. URL: https://doi.org/10.1109/LICS.2019.8785792.
  6. W. Baur and V. Strassen. The complexity of partial derivatives. Theor. Comput. Sci., 22, 1983. URL: https://doi.org/10.1016/0304-3975(83)90110-X.
  7. A. Blass, Y. Gurevich, and S. Shelah. On polynomial time computation over unordered structures. Journal of Symbolic Logic, 67(3):1093-1125, 2002. Google Scholar
  8. J-Y. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. Google Scholar
  9. A. Dawar. The nature and power of fixed-point logic with counting. ACM SIGLOG News, 2(1):8-21, 2015. Google Scholar
  10. A. Dawar and D. Richerby. The power of counting logics on restricted classes of finite structures. In CSL 2007:Computer Science Logic, volume 4646 of LNCS, pages 84-98. Springer, 2007. Google Scholar
  11. A. Dawar and P. Wang. Definability of semidefinite programming and Lasserre lower bounds for CSPs. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, 2017. URL: https://doi.org/10.1109/LICS.2017.8005108.
  12. A. Dawar and G. Wilsenach. Symmetric circuits for rank logic. In 27th EACSL Annual Conference on Computer Science Logic, CSL 2018, pages 20:1-20:16, 2018. Google Scholar
  13. L. Denenberg, Y. Gurevich, and S. Shelah. Definability by constant-depth polynomial-size circuits. Information and Control, 70:216-240, 1986. Google Scholar
  14. M. A. Forbes, M. Kumar, and R. Saptharishi. Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity. In 31st Conference on Computational Complexity, CCC 2016, pages 33:1-33:19, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.33.
  15. D. Grigoriev and M. Karpinski. An exponential lower bound for depth 3 arithmetic circuits. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pages 577-582, 1998. URL: https://doi.org/10.1145/276698.276872.
  16. B. Holm. Descriptive Complexity of Linear Algebra. PhD thesis, University of Cambridge, 2010. Google Scholar
  17. M. Jerrum and M. Snir. Some exact complexity results for straight-line computations over semirings. J. ACM, 29:874-897, 1982. URL: https://doi.org/10.1145/322326.322341.
  18. N. Kayal and R. Saptharishi. A selection of lower bounds for arithmetic circuits. In M. Agrawal and V. Arvind, editors, Perspectives in Computational Complexity. Birkhäuser Basel, 2014. Google Scholar
  19. J.M. Landsberg and N. Ressayre. Permanent v. determinant: An exponential lower bound assuming symmetry. In Proc. ACM Conference on Innovations in Theoretical Computer Science, pages 29-35. ACM, 2016. URL: https://doi.org/10.1145/2840728.2840735.
  20. M. Otto. The logic of explicitly presentation-invariant circuits. In Computer Science Logic, 10th International Workshop, CSL '96, Annual Conference of the EACSL, pages 369-384, 1996. Google Scholar
  21. A. Shpilka and A. Wigderson. Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity, 10:1-27, 2001. URL: https://doi.org/10.1007/PL00001609.
  22. A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. URL: https://doi.org/10.1561/0400000039.
  23. L. G. Valiant. Completeness classes in algebra. In Proceedings of the 11h Annual ACM Symposium on Theory of Computing STOC, pages 249-261, 1979. URL: https://doi.org/10.1145/800135.804419.
  24. H. Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. URL: https://doi.org/10.1007/978-3-662-03927-4.
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