Limits of Symmetric Computation

The problem of separating the complexity classes P and NP is a central open question in theoretical computer science and one of the most famous open problems in all of mathematics. While a vast field of research in computational complexity has developed around it, we do not as of now have any credible research agenda that offers an approach to this problem. In order to prove super-polynomial lower bounds for NP-hard search problems, we need three ingredients: (1) A classification of structure in search spaces; (2) A classification of polynomial-time algorithms; (3) Mathematical tools for dealing with these. There have been recent developments in theoretical computer science that have advanced our understanding on the first two. The dichotomy theorem for constraint satisfaction problems provides a thorough classification of search spaces for one collection of well-behaved problems, and the developing theory of symmetric computation reveals fundamental limitations of some polynomial-time algorithms, spanning circuit complexity, combinatorial optimization and hardness of approximation.

In this project we exploit a striking convergence of these two to obtain further groundbreaking results. We aim at a complete classification of constraint solving algorithms by the symmetries they preserve. We propose a sweeping re-evaluation of the foundations of algorithmic complexity in the light of symmetry. The theory of symmetric computation that will be developed will yield new lower bounds in circuit complexity and approximability as well as new insights into the graph isomorphism problem. This will build on tools from a number of mathematical areas - representation theory, algebraic topology and category theory.