The Finite-Model-Theoretic Complexity of Symmetric Circuits

Prelegent(ci)

Benedikt Pago

Afiliacja

University of Cambridge

Język referatu

angielski

Termin

8 kwietnia 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

The Finite-Model-Theoretic Complexity of Symmetric Circuits

Seminarium

Seminarium „Teoria automatów”

---

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.

---