A single, decades-old problem in computer science—how to efficiently colour a graph with a limited number of colours—remains unsolved, and this project aims to crack it using a new mathematical framework. The problem is a classic example of a constraint satisfaction problem (CSP), where the goal is to assign values (colours) to variables (nodes) while respecting certain rules (no two connected nodes share a colour). For many CSPs, computer scientists know how hard it is to find a perfect solution, but they know far less about how hard it is to find a *good enough* solution when a perfect one exists. This gap in knowledge is the project's target. The researcher will use a recent framework called "promise CSPs" to develop new algorithms and new proofs of hardness for these satisfiable-but-approximate problems. If successful, the work will resolve the graph colouring problem and deepen the fundamental understanding of computational complexity. This is curiosity-driven fundamental science. While it has no immediate practical application, past work on CSPs has underpinned everything from scheduling software to error-correcting codes. A clearer picture of what computers can and cannot approximate could, in the long run, reshape how we design algorithms for logistics, network design, and combinatorial optimisation.
View original technical description
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. 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.
Plain English summaries and category classifications on this site are generated by AI and may not perfectly reflect the original research.
Is something wrong? Let us know