Complexity of CSPs: Exact and Approximation

by Prasad Raghavendra.

Oded's comments

While the main result asserts that, for every CSP and every epsilon, there exists a polynomial-time algorithm that gets within epsilon of the approximation factor that is UGJ-hard, I was most impressed by the fact that this seemingly optimal approximation factor can be efficiently approximated.

The original abstract

Constraint Satisfaction Problem (CSP) such as 3-SAT, Horn-SAT is specified by a set of predicates. In the exact version, the goal is to find out if an instance of the CSP is completely satisfiable or unsatisfiable. In the approximate version, the goal is to find an assignment that satisfies the maximum number of constraints. The algebraic dichotomy conjecture of Jeavons-Bulatov is an attempt at characterizing exactly for which CSPs the exact version is in P. Roughly speaking, this conjecture asserts that CSPs that are in P are characterized by non-trivial operations that take feasible solutions to an instance, to another feasible solution. For example, adding three feasible solutions to a linear system over F_2 yields another feasible solution, therefore linear equations are easy to solve. The Unique Games Conjecture of Khot yields the threshold of hardness for approximation versions of every CSP. In this work, we show that the Unique games conjecture is indeed a natural generalization of the algebraic dichotomy conjecture from exact-CSP to approximate CSP. In a way, it yields a natural explanation as to where the approximation threshold for a CSP arises from.

Back to list of Oded's choices.