Per Austrin

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.

Friday, October 26, 2007 4:00 PM 5130 Upson Hall		Theory Seminar Fall 2007 CS 789
	Per Austrin KTH
	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.