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.

The project builds on my ERC Starting Grant PowAlgDO.

** Principal Investigator **

** Postdoctoral Research Fellows **

- Silvia Butti, since 23 January 2023
- Lorenzo Ciardo, since 1 July 2022

** DPhil Students **

- Tamio-Vesa Nakajima, since 1 July 2022

** Project Summary **

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.

** Visitors **

- Andrei Krokhin, 3-6 October 2022
- Marcin Kozik, 1 July 2022 - 31 July 2022

** Papers **