Advances in circuit lower bounds via symmetry

In different branches of circuit complexity, the long-term goal is to prove lower bounds on the circuit size of explicit functions. Typically, progress is made by establishing lower bounds for syntactically restricted circuit models and then gradually trying to relax these restrictions. 
Symmetry as a restriction is especially interesting for this purpose because it allows to prove strong lower bounds while at the same time retaining a lot of the expressive power of the model.

I will discuss two symmetry-based lower bound results in this talk. The first one is in algebraic complexity, a programme initiated by Valiant in 1979 that classifies families of polynomials, such as the determinant and permanent, according to their circuit complexity. One of the major open problems in this field is to separate formulas (VF), algebraic branching programs (VBP), and circuits (VP) with respect to their expressive power. Our lower bounds achieve this separation in the symmetric setting.

The second result concerns the limitations of Boolean circuits with modular counting gates. A big open conjecture in this topic asserts that CC^0 is not equal to ACC^0, which is saying that Boolean connectives cannot be simulated efficiently by constant-depth circuits with modular counting gates. Again, our result confirms this conjecture under suitable symmetry assumptions.

I will also give an overview of the proof techniques for symmetric circuit lower bounds, which combine permutation group theory, algebra, and graph theory in interesting ways.

Based on joint work with Anuj Dawar, Prateek Dwivedi and Tim Seppelt.