On the Complexity of Unique Games and Graph Expansion

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.