IEEE FOCS 2010
TechTalks from event: IEEE FOCS 2010
51st Annual IEEE Symposium on Foundations of Computer Science
Subexponential Algorithms for Unique Games and Related problemsWe give subexponential time approximation algorithms for the unique games and the small set expansion problems. Specifically, for some absolute constant c, we give:
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 refusing 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).
Nevanlinna Prize Talk. Laplacian GemsI will explain some of the most interesting applications of solving linear equations in Laplacian matrices as well as some of the most interesting ideas that have been used in algorithms that solve these equations. The main applications will come from machine learning and optimization. The algorithmic ideas I discuss will include local clustering, sparsification, low-stretch spanning trees, and an under-appreciated technique of Lovasz and Simonovits for bounding the convergence rate of Markov chains.