TIME: 1:30-2:30 pm,  Tuesday, October 14, 2008

PLACE: CSE 503  

SPEAKER: Prasad Raghavendra
         University of Washington

TITLE: Optimal Algorithms and Inapproximability Results for every CSP?


ABSTRACT: 
Semidefinite Programming(SDP) is one of the strongest algorithmic techniques
used in the design of approximation algorithms. In recent years, the 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 the 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.