New Approaches to Approximability of Satisfiable Problems

约束满足问题（CSP）推动了理论计算机科学中一些最有影响力的发展，从NP完全性到PCP定理，再到半定规划算法，再到唯一博弈猜想。易处理的决策CSP的数学结构，以及精确可解和可逼近的Max-CSP，现在已知与解空间的某些形式的高阶对称性有关。虽然唯一对策猜想在加深我们对CSP不可逼近性的理解方面具有极大的影响力，但对可满足问题的可逼近性却知之甚少。一个经典的例子是近似图着色问题，尽管自20世纪70年代以来一直在努力，但其复杂性仍然是开放的。一个非常近期的承诺CSP的工作提出了一个框架下研究这些问题的一把伞，并启动了第一步，这个项目的目标是释放新框架的全部力量：开发新的方法来证明硬度，设计新的算法范例，并攻击主要的开放问题，如图着色问题。由于计算复杂性的基本性质，该项目的成功也将有利于一些相关领域，从组合优化到随机算法和组合学。该项目的目标是释放新框架的全部力量：开发新的方法来证明硬度，设计新的算法范例，并解决主要的开放问题，如图着色问题。由于计算复杂性的基本性质，该项目的成功也将使许多相关领域受益，从组合优化到随机算法和组合学。

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.