New Approaches to Approximability of Satisfiable Problems

点击翻译按钮获取中文摘要

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.