Lower Bounds for Symmetric Algebraic Circuits

IANUJ DAWAR, Lower Bounds for Symmetric Algebraic Circuits. Department of Computer Science and Technology, University of Cambridge, U.K.. E-mail:[email protected]. URL Address:https://www.cst.cam.ac.uk/people/ad260. Algebraic circuits (also known as arithmetic circuits) are a model for computing polynomial functions over an arbtrary field. Valiant’s conjecture that VP is different from VNP is sometimes called an algebraic analogue of the conjecture that P is different from NP and has been an open question for nearly as long. It amounts to showing that algebraic circuits for computing the permanent of a matrix are necessarily of super-polynomial size. We are able to show lower bounds on circuits computing the permanent when restricted to certain symmetry conditions. With a natural notion of symmetry, this gives an exponential separation between the size of circuits computing the permanent and those computing the determinant. The result is sensitive to the choice of symmetries considered. In this talk, I give a general introduction to algebraic circuits and Valiant’s conjecture. I explain and motivate the symmetry restrictions and explore the lower bounds that can be established. I also give an overview of the proof methods, which bring together combinatorial techniques with methods from finite model theory. This is based on two papers joint with Gregory Wilsenach [2, 3] and one with Benedikt Pago and Tim Seppelt [1]. [1] A. Dawar, B. Pago, and T. Seppelt. Symmetric algebraic circuits and homomorphism polynomials. arXiv 2502.06740, 2025. [2] A. Dawar and G. Wilsenach. Symmetric Arithmetic Circuits. In 47th International Colloquium on Automata, Languages, and Programming, volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1–36:18, 2020. [3] A. Dawar and G. Wilsenach. Lower bounds for symmetric circuits for the determinant. In 13th Innovations in Theoretical Computer Science Conference, ITCS, volume 215 of LIPIcs, pages 52:1–52:22. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2022.