on Tuesday, May 11, 2010 at 16:00
Boaz Barak (Princeton University) will speak on
Subexponential Algorithms for Unique Games and Related Problems
Abstract:
1. An $\exp(kn^{\epsilon})$-time algorithm that, given as input a $k$-alphabet
unique game on $n$ variables that has an assignment satisfying $1-\epsilon^c$
fraction of its constraints, outputs an assignment satisfying $1-\epsilon$
fraction of the constraints.
2. An $\exp(n^{\epsilon/\delta})$-time algorithm that, given as input an
$n$-vertex regular graph that has a set $S$ of $\delta n$ vertices with edge
expansion at most $\epsilon^c$ outputs a set $S'$ of at most $\delta n$
vertices with edge expansion at most $\epsilon$.
We also obtain a subexponential algorithm with improved approximation for the
Multi-Cut problem, as well as subexponential algorithms with improved
approximations to Max-Cut, Sparsest-Cut and Vertex-Cover on some interesting
subclasses of instances.
Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve
approximation guarantees such as ours for unique games. While our results stop
short of refuting the UGC, they do suggest that Unique Games is significantly
easier than NP-hard problems such as 3SAT, 3LIN, Label Cover and more, that are
believed not to have a subexponential algorithm achieving a non-trivial
approximation ratio.
The main component in our algorithms is a new result on graph decomposition
that may have other applications. Namely we show that for every $\delta>0$ and
a regular $n$-vertex graph $G$, by changing at most $\delta$ fraction of $G$'s
edges, one can break $G$ into disjoint parts so that the induced graph on each
part has at most $n^{\epsilon}$ eigenvalues larger than $1-\eta$ (where
$\epsilon,\eta$ depend polynomially on $\delta$). Our results are based on
combining this decomposition with previous algorithms for unique games on
graphs with few large eigenvalues (Kolla and Tulsiani 2007, Kolla 2010).
Joint work with Sanjeev Arora and David Steurer.