[1]   Miklós Ajtai: Recursive construction for 3-regular expanders. Combinatorica, 14(4):379–416, 1994. [doi:10.1007/BF01302963]

[2]   Matthew Anderson and Anuj Dawar: On symmetric circuits and fixed-point logics. Theory Computing Sys., 60(3):521–551, 2017. Preliminary version in STACS’14. [doi:10.1007/s00224-016-9692-2]

[3]   Matthew Anderson, Anuj Dawar, and Bjarki Holm: Solving linear programs without breaking abstractions. J. ACM, 62(6):48:1–26, 2015. [doi:10.1145/2822890]

[4]   Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky: On Weisfeiler–Leman invariance: Subgraph counts and related graph properties. J. Comput. System Sci., 113:42–59, 2020. Preliminary version in FCT’19. [doi:10.1016/j.jcss.2020.04.003]

[5]   Albert Atserias, Anuj Dawar, and Joanna Ochremiak: On the power of symmetric linear programs. J. ACM, 68(4), 2021. Preliminary version in LICS’19. [doi:10.1145/3456297]

[6]   Walter Baur and Volker Strassen: The complexity of partial derivatives. Theoret. Comput. Sci., 22(3):317–330, 1983. [doi:10.1016/0304-3975(83)90110-X]

[7]   Markus Bläser and Gorav Jindal: On the complexity of symmetric polynomials. In Proc. 10th Innovations in Theoret. Comp. Sci. Conf. (ITCS’19), pp. 47:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.47]

[8]   Andreas Blass, Yuri Gurevich, and Saharon Shelah: On polynomial time computation over unordered structures. J. Symbolic Logic, 67(3):1093–1125, 2002. [doi:10.2178/jsl/1190150152]

[9]   Jin-Yi. Cai, Martin Fürer, and Neil Immerman: An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389–410, 1992. [doi:10.1007/BF01305232]

[10]   Anuj Dawar: The nature and power of fixed-point logic with counting. ACM SIGLOG News, 2(1):8–21, 2015. [doi:10.1145/2728816.2728820]

[11]   Anuj Dawar: On symmetric and choiceless computation. In Mohammad Taghi Hajiaghayi and Mohammad Reza Mousavi, editors, Topics in Theoretical Computer Science (TTCS’15), pp. 23–29. Springer, 2016. [doi:10.1007/978-3-319-28678-5_2]

[12]   Anuj Dawar and David Richerby: The power of counting logics on restricted classes of finite structures. In Proc. 21st Internat. Workshop Computer Science Logic (CSL’07), pp. 84–98. Springer, 2007. [doi:10.1007/978-3-540-74915-8_10]

[13]   Anuj Dawar and Pengming Wang: Definability of semidefinite programming and Lasserre lower bounds for CSPs. In Proc. 32nd Ann. ACM/IEEE Symp. on Logic in Computer Science (LICS’17), pp. 1–12. ACM Press, 2017. [doi:10.1109/LICS.2017.8005108]

[14]   Anuj Dawar and Gregory Wilsenach: Symmetric arithmetic circuits. In Proc. 47th Internat. Colloq. on Automata, Languages, and Programming (ICALP’20), pp. 36:1–18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ICALP.2020.36]

[15]   Anuj Dawar and Gregory Wilsenach: Lower bounds for symmetric circuits for the determinant. In Proc. 13th Innovations in Theoret. Comp. Sci. Conf. (ITCS’22), pp. 52:1–22. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2022. [doi:10.4230/LIPIcs.ITCS.2022.52]

[16]   Anuj Dawar and Gregory Wilsenach: Symmetric circuits for rank logic. ACM Trans. Comput. Logic, 23(1):6:1–35, 2022. [doi:10.1145/3476227]

[17]   Larry Denenberg, Yuri Gurevich, and Saharon Shelah: Definability by constant-depth polynomial-size circuits. Inform. Control, 70(2–3):216–240, 1986. [doi:10.1016/S0019-9958(86)80006-7]

[18]   Michael A. Forbes, Mrinal Kumar, and Ramprasad Saptharishi: Functional lower bounds for arithmetic circuits and connections to Boolean circuit complexity. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 33:1–19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.33]

[19]   Dima Grigoriev and Marek Karpinski: An exponential lower bound for depth 3 arithmetic circuits. In Proc. 30th STOC, pp. 577–582. ACM Press, 1998. [doi:10.1145/276698.276872]

[20]   Frank Harary: Determinants, permanents and bipartite graphs. Math. Magazine, 42(3):146–148, 1969. [doi:10.1080/0025570X.1969.11975950]

[21]   Bjarki Holm: Descriptive Complexity of Linear Algebra. Ph. D. thesis, U. Cambridge, 2010. Available at U. Cambridge.

[22]   Mark Jerrum and Marc Snir: Some exact complexity results for straight-line computations over semirings. J. ACM, 29(3):874–897, 1982. [doi:10.1145/322326.322341]

[23]   Neeraj Kayal and Ramprasad Saptharishi: A selection of lower bounds for arithmetic circuits. In Manindra Agrawal and Vikram Arvind, editors, Perspectives in Computational Complexity, pp. 77–115. Birkhäuser, 2014. Available at Microsoft Research. [doi:10.1007/978-3-319-05446-9_5]

[24]   Joseph M. Landsberg and Nicolas Ressayre: Permanent v. determinant: An exponential lower bound assuming symmetry and a potential path towards Valiant’s conjecture. Diff. Geom. Appl, 55:146–166, 2017. Preliminary version in ITCS’16. [doi:10.1016/j.difgeo.2017.03.017]

[25]   Martin Otto: The logic of explicitly presentation-invariant circuits. In Proc. 10th Internat. Workshop Computer Science Logic (CSL’96), pp. 369–384. Springer, 1996. [doi:10.1007/3-540-63172-0_50]

[26]   Benjamin Rossman: Subspace-invariant AC⁰ formulas. Logical Methods Comp. Sci., 15:3:1–12, 2019. [doi:10.23638/LMCS-15(3:3)2019]

[27]   Amir Shpilka and Avi Wigderson: Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complexity, 10:1–27, 2001. [doi:10.1007/PL00001609]

[28]   Amir Shpilka and Amir Yehudayoff: Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comp. Sci., 5(3–4):207–388, 2010. [doi:10.1561/0400000039]

[29]   Leslie G. Valiant: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261. ACM Press, 1979. [doi:10.1145/800135.804419]

[30]   Leslie G. Valiant and Sven Skyum: Fast parallel computation of polynomials using few processors. In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCS’81), pp. 132–139. Springer, 1981. [doi:10.1007/3-540-10856-4_79]

[31]   Heribert Vollmer: Introduction to Circuit Complexity – A Uniform Approach. Springer, 1999. [doi:10.1007/978-3-662-03927-4]