Friday, October 26, 2007
4:00 PM
5130 Upson Hall
  Theory Seminar
Fall 2007
CS 789

Per Austrin


Beating Semidefinite Programming Means
Beating The Unique Games Conjecture

During the last few years, there have been several results of the form "if the Unique Games Conjecture is true, then problem X can not be approximated better than what is achieved by algorithm Y, based on semidefinite programming", indicating a strong connection between the UGC and the limitations of SDP-based approximation algorithms.

For 2-CSP problems in particular this connection has been very evident, with the optimal parameters for the hardness reductions for Max Cut and Max 2-Sat coming directly from the analysis of the best SDP-based approximation algorithms for the problems.

We generalize these results, by considering an arbitrary boolean 2-CSP (or more generally, an arbitrary nonnegative objective function on two boolean variables), and show that a set of "obstructions" towards obtaining a good rounding procedure for the SDP relaxation can be translated into a matching UG-hardness result. We also show that, under a certain conjecture on the nature of worst-case angles for the SDP relaxation, this result is tight. This conjecture is supported by all previous results for specific 2-CSPs.