Title : Optimal Algorithms and Inapproximability Results for every CSP?

Speaker: Prasad Raghavendra, Univ. of Washington. 

ABSTRACT :

Semidefinite Programming(SDP) is one of the strongest algorithmic techniques used in the design of 

approximation algorithms.  In recent years, Unique Games Conjecture(UGC) has proved to be intimately 

connected to the limitations of Semidefinite Programming.

Making this connection precise, we show the following result :

If UGC is  true, then for every constraint satisfaction problem(CSP) the best approximation ratio is 

 given by certain simple SDP.  Specifically, we show a generic  conversion  from SDP integrality gap 

instances to UGC hardness results.   This result  holds both for maximization and minimization 

problems over arbitrary finite domains.

Using this connection between integrality gaps and hardness results we

obtain a generic polynomial-time algorithm for all CSPs.  Assuming the Unique Games Conjecture, this 

algorithm achieves the optimal approximation ratio for every CSP.

Unconditionally, for all 2-CSPs the algorithm achieves an approximation ratio equal to the 

integrality gap of the natural SDP.  Thus the algorithm achieves at least as good an approximation 

ratio as the best known algorithms for several problems like MaxCut, Max2SAT and Unique Games.