AF: Small: CSPs --- Approximability versus Time

提出的研究解决了非常基本的优化任务的算法复杂性-网络划分，求解线性方程，满足逻辑公式，以及其他约束满足问题（csp）。先前对这类问题的研究表明，要么存在产生一定质量解的非常高效的算法，要么存在达到完美质量的非常低效的算法。然而，最近的研究，包括一种名为“SOS方法”的新进化算法技术，表明在效率和质量之间进行重要权衡的可能性。具体来说，这项工作有以下三个技术目标：1。进一步了解SOS方法的力量和局限性。改进csp的已知np -硬度结果，重点是给出反对次指数时间算法的证据。寻找新的随机CSP实例家族——特别是“小集扩展”或“独特游戏”实例——这在算法上似乎很困难。这项研究最终将对算法的实践产生广泛的影响；更具体地说，是关于开发（并排除）真正有效的启发式方法来解决约束满足问题。寻找新的硬表面CSP实例族的研究也可能导致密码学的进步。

The proposed research addresses the algorithmic complexity of very basic optimization tasks - network partitioning, solving linear equations, satisfying logical formulas, and other constraint satisfaction problems (CSPs). Previous research on these kinds of problems suggested the existence of either very efficient algorithms yielding solutions of a certain quality, or very inefficient algorithms achieving perfect quality. However recent research, including a newly evolving algorithmic technique called the "SOS method", suggests the possibility of a nontrivial tradeoff between efficiency and quality. Specifically, the work has the following three technical goals:1. Further understand the power and the limitations of the SOS Method.2. Improve the known NP-hardness results for CSPs, with an emphasis on giving evidence against subexponential-time algorithms.3. Find new random families of CSP instances - especially "Small-Set Expansion" or "Unique Games" instances - which seem algorithmically difficult.The research will ultimately have broad impact on the practice of algorithms; more specifically, on developing (and ruling out) truly efficient heuristics for solving constraint satisfaction problems. It is also possible that the research on finding new families of hard-seeming CSP instances may lead to advances in cryptography.