This project was awarded as an ERC Consolidator Grant in March 2022 as the only ERC CoG awarded to the University of Oxford across all disciplines and the only ERC CoG awarded in Computer Science and Informatics (PE6 panel) in the UK in the 2021 round. Due to the non-association of the UK to the ERC, this grant was transformed into an equivalent UKRI ERC Guarantee Grant. The project runs from 1 July 2022 through 30 June 2027 in the Department of Computer Science at the University of Oxford.

The project builds on my ERC Starting Grant PowAlgDO.

Constraint satisfaction problems (CSPs) have driven some of the most influential developments in theoretical computer science, from NP-completeness to the PCP theorem to semidefinite programming algorithms to the Unique Games Conjecture. The mathematical structure of tractable decision CSPs, as well as exactly solvable and approximable Max-CSPs, is now known to be linked to certain forms of higher-order symmetries of solution spaces. While the Unique Games Conjecture has been extremely influential in sharpening our understanding of inapproximability of CSPs, much less is known about approximability of problems that are satisfiable.

This proposal is concerned with approximability of satisfiable CSPs. A classic example is the approximate graph colouring problem, whose complexity is still open despite sustained effort since the 1970s. A very recent line of work on promise CSPs proposed a framework for studying such problems under one umbrella and initiated the first steps.

The goal of this project is to unleash the full power of the new framework: to develop novel approaches for proving hardness, to devise new algorithmic paradigms, and to attack major open problems, such as the graph colouring problem. Due to the fundamental nature of computational complexity, success of the project will also benefit a number of related areas, ranging from combinatorial optimisation to randomised algorithms and combinatorics.