ERC Consolidator Grant · 2017
Symmetry in Computational Complexity
The last 20 years of rapid development in the computational-theoretic aspects of the fixed-language Constraint Satisfaction Problems (CSPs) has been fueled by a connection between the complexity and a certain concept capturing symmetry of computational problems in this class. My vision is that this connection will eventually evolve into the organizing principle of computational complexity and will lead to solutions of fundamental problems such as the Unique Games Conjecture or even the P-versus-NP problem. In order to break through the current limits of this algebraic approach, I will concentrate on specific goals designed to (A) discover suitable objects capturing symmetry that reflect the…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.