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.

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.