You are not logged in |
The Finite-Model-Theoretic Complexity of Symmetric Circuits
- Speaker(s)
- Benedikt Pago
- Affiliation
- University of Cambridge
- Language of the talk
- English
- Date
- April 8, 2026, 2:15 p.m.
- Room
- room 5440
- Title in Polish
- The Finite-Model-Theoretic Complexity of Symmetric Circuits
- Seminar
- Seminar Automata Theory
In various areas of complexity theory, there are long-standing open conjectures that are widely believed to be true, but notoriously hard to settle.
The obstacle is our apparent inability to prove lower bounds that would be strong enough to separate complexity classes.
In this talk I will explain how techniques from logic, specifically finite model theory, can be harnessed to enable new progress on lower bounds in different areas of circuit complexity. For this, it is crucial to restrict attention to symmetric circuits - a natural and still surprisingly powerful model.
I will present a survey of my work on symmetric circuits in the context of algebraic complexity, proof complexity, and Boolean circuits with modular counting gates.
In particular, I will discuss the surprisingly tight connections between symmetric algebraic circuits and the theory of graph homomorphism counting, and how these results open up avenues for future research on circuit lower bounds.
