Thursday, March 06, 2014

Favorite Theorems: Unique Games

Michel Goemans and David Williamson made a splash in the 90's using semidefinite programming to give a new approximation algorithm for the max-cut problem, a ratio of 2θ/(π(1-cos(θ)) minimized over θ between 0 and π, approximately 0.87856. Hard to believe that this ratio is tight, but it is assuming the unique games conjecture.
The first paper showed that the Goemans-Williamson bound was tight assuming the unique games conjecture and a "majority is stablest conjecture", the last says very roughly that the most robust election scheme is a simple majority. The second paper, which followed soon thereafter, proved an invariance property that implies, among other things, that indeed majority is stablest.

Khot and Oded Regev show that under the unique games conjecture that essentially the best algorithm for approximating vertex cover is to take all the vertices involved in a maximal matching.

Prasad Raghavendra gives a simple semidefinite programming approximation algorithm for any constraint satisfaction problem which is optimal under the UGC.

Sanjeev Arora, Boaz Barak and David Steurer describe an algorithm that given a unique game where 1-δ fraction of the edges can be satisfied, you can in time 2npoly(δ) find a coloring that satisfies a constant fraction of edges. This may or may not give evidence against the UGC.

Luca Trevisan has a nice recent survey on the unique games conjecture, covering much of the above and more, including beautiful connections between unique games and semidefinite programming.

1 comment:

  1. As Lance has already tweeted, the STOC 2014 accepted papers list has been out for about a week. Though it currently re-directs to the local arrangements website at Columbia, this is the first use of the web address which will be the future direct link to all STOC conferences.