AF: Small: CSPs --- Approximability versus Time

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.