Document Open Access Logo

Lower Bounds for Symmetric Circuits for the Determinant

Authors Anuj Dawar , Gregory Wilsenach

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.52.pdf
  • Filesize: 0.84 MB
  • 22 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 by EPSRC grant EP/S03238X/1.

Acknowledgements

We are grateful to Albert Atserias for useful discussions on the construction in Section 5.2

Cite AsGet BibTex

Anuj Dawar and Gregory Wilsenach. Lower Bounds for Symmetric Circuits for the Determinant. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 52:1-52:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.52

Abstract

Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithmetic circuits and show an exponential separation between the sizes of symmetric circuits for computing the determinant and the permanent. The symmetry restriction is that the circuits which take a matrix input are unchanged by a permutation applied simultaneously to the rows and columns of the matrix. Under such restrictions we have polynomial-size circuits for computing the determinant but no subexponential size circuits for the permanent. Here, we consider a more stringent symmetry requirement, namely that the circuits are unchanged by arbitrary even permutations applied separately to rows and columns, and prove an exponential lower bound even for circuits computing the determinant. The result requires substantial new machinery. We develop a general framework for proving lower bounds for symmetric circuits with restricted symmetries, based on a new support theorem and new two-player restricted bijection games. These are applied to the determinant problem with a novel construction of matrices that are bi-adjacency matrices of graphs based on the CFI construction. Our general framework opens the way to exploring a variety of symmetry restrictions and studying trade-offs between symmetry and other resources used by arithmetic circuits.

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. Anderson and A. Dawar. On symmetric circuits and fixed-point logics. Theory Comput. Syst., 60(3):521-551, 2017. Google Scholar
  2. A. Atserias, A. Dawar, and J. Ochremiak. On the power of symmetric linear programs. J.ACM, 2021. to appear. arxiv:1901.07825. Google Scholar
  3. A. Blass, Y. Gurevich, and S. Shelah. Choiceless polynomial time. Annals of Pure and Applied Logic, 100(1):141-187, 1999. URL: https://doi.org/10.1016/S0168-0072(99)00005-6.
  4. Béla Bollobás. The distribution of the maximum degree of a random graph. Discret. Math., 32:201-203, 1980. URL: https://doi.org/10.1016/0012-365X(80)90054-0.
  5. G. Brito, I. Dumitriu, and K. D. Harris. Spectral gap in random bipartite biregular graphs and applications. Combinatorics, Probability and Computing, 2021. to appear. arXiv:1804.07808. Google Scholar
  6. P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory. Springer, Berlin, Heidelberg, 1 edition, 1997. Google Scholar
  7. 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
  8. A. Dawar. On symmetric and choiceless computation. In Mohammad Taghi Hajiaghayi and Mohammad Reza Mousavi, editors, Topics in Theoretical Computer Science, pages 23-29, Cham, 2016. Springer International Publishing. Google Scholar
  9. A. Dawar. Symmetric computation (invited talk). In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, 2020. URL: https://doi.org/10.4230/LIPIcs.CSL.2020.2.
  10. 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. Full version at arXiv:1804.02939. URL: https://doi.org/10.4230/LIPIcs.CSL.2018.20.
  11. A. Dawar and G. Wilsenach. Symmetric Arithmetic Circuits. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1-36:18, 2020. Full version at arXiv:2002.06451. Google Scholar
  12. A. Dawar and G. Wilsenach. Lower bounds for symmetric circuits for the determinant, 2021. URL: http://arxiv.org/abs/2107.10986.
  13. J.D. Dixon and B. Mortimer. Permutation Groups. Graduate Texts in Mathematics. Springer New York, 1996. URL: https://books.google.co.uk/books?id=4QDpFN6k61EC.
  14. 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.
  15. M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, volume 47 of Lecture Notes in Logic. Cambridge University Press, 2017. Google Scholar
  16. M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic. Cambridge University Press, 2017. Google Scholar
  17. F. Harary. Determinants, permanents and bipartite graphs. Mathematics Magazine, 42:146-148, 1969. URL: https://doi.org/10.1080/0025570X.1969.11975950.
  18. L. Hella. Logical hierarchies in PTIME. Information and Computation, 129(1):1-19, 1996. Google Scholar
  19. B. Holm. Descriptive Complexity of Linear Algebra. PhD thesis, University of Cambridge, 2010. Google Scholar
  20. S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  21. 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.
  22. 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
  23. 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.
  24. M. Molloy, H. D. Robalewska, R. W. Robinson, and N. C. Wormald. 1-factorizations of random regular graphs. Random Struct. Algorithms, 10:305-321, 1997. Google Scholar
  25. H.J. Ryser. Combinatorial Mathematics, volume 14. Mathematical Association of America, 1 edition, 1963. Google Scholar
  26. 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.
  27. 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 Imprint Privacy Contact