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.