On the complexity of Unique Games and graph expansion

Dissertation.

PDF

Honorable Mention for ACM Doctoral Dissertation Award 2011

abstract

Understanding the complexity of approximating basic optimization problems is one of the grand challenges of theoretical computer science. In recent years, a sequence of works established that Khot's Unique Games Conjecture, if true, would settle the approximability of many of these problems, making this conjecture a central open question of the field.

The results of this thesis shed new light on the plausibility of the Unique Games Conjecture, which asserts that a certain optimization problem, called Unique Games, is hard to approximate in a specific regime.

On the one hand, we give the first confirmation of this assertion for a restricted model of computation that captures the best known approximation algorithms. The results of this thesis also demonstrate an intimate connection between the Unique Games Conjecture and approximability of graph expansion. In particular, we show that the Unique Games Conjecture is true if the expansion of small sets in graphs is hard to approximate in a certain regime. This result gives the first sufficient condition for the truth of the conjecture based on the inapproximability of a natural combinatorial problem.

On the other hand, we develop efficient approximation algorithms for certain classes of Unique Games instances, demonstrating that several previously proposed variants of the Unique Games Conjecture are false.

Finally, we develop a subexponential-time algorithm for Unique Games, showing that this problem is significantly easier to approximate than NP-hard problems like Max 3-Sat, Max 3-Lin, and Label Cover, which are unlikely to have subexponential-time algorithm achieving a non-trivial approximation guarantee. This algorithm also shows that the inapproximability results based on the Unique Games Conjecture do not rule out subexponential-time algorithms, opening the possibility for such algorithms for many basic optimization problems like Max Cut and Vertex Cover.

At the heart of our subexponential-time algorithm for Unique Games lies a novel algorithm for approximating the expansion of graphs across different scales, which might have applications beyond Unique Games, especially in the design of divide-and-conquer algorithms.

keywords

  • Unique Games Conjecture
  • small-set expansion
  • approximation algorithms
  • lower bounds
  • hardness reduction
  • semidefinite programming
  • eigenvalues