Recent results regarding the Unique Games Conjecture
STOC 2012 Workshop
Saturday, May 19th at New York University
Warren Weaver Hall, Room 109
Organized by Sanjeev Arora and Moses Charikar,
Center for Computational Intractability
and Princeton University
Khot’s Unique Games Conjecture (UGC) —which asserts the NP-hardness of approximating a very simple constraint satisfaction problem— has assumed a central role in the effort to understand the optimal approximation ratios achievable for various NP-hard problems. It has been found to imply that the optimal approximation ratio is exactly the integrality gap of the standard SDP (semidefinite programming) relaxations. The past few years have seen a flurry of results, including surprises such as a subexponential-time approximation algorithm, as well as algorithms for all “natural” families of instances we can think of. The workshop introduces some of the key developments and is geared to non-experts.
Schedule and abstracts below. See http://cs.nyu.edu/~stoc2012/tutorials.htm for more information about STOC tutorials.
Warren Weaver Hall is on the South East corner of West 4th Street and Mercer Street (walk East from the South end of Washington Square park for two short blocks); the entrance in on Mercer Street. The address is 251 Mercer St.
1:30-2:20 : Subhash Khot: Survey of UGC and our current understanding.
2:20-3:30: Barak, Raghavendra, and Steurer. Algorithms for unique games and related problems, rounding algorithms for SDP hierarchies, spectral algorithms.
Part I of Survey.
3:30—4:00: Coffee break
4:00—4:45: Part II of BRS survey
4:45—5:30: Konstanti Makarychev: Algorithms for semirandom instances.
Title: On the power of semidefinite programming hierarchies: Algorithms and Integrality Gaps.
Speakers: Boaz Barak, Prasad Raghavendra, David Steurer
Abstract: The study of the unique games conjecture (UGC) has led to deeper understanding of the power of semidefinite programs (SDP) — in form of new algorithms, integrality gap constructions and tight hardness results. In this tutorial, we will survey some of the recent advances in approximation algorithms based on SDP hierarchies, fuelled by the
UGC. The talk will include a gentle algorithmic introduction to SDP hierarchies and their limits.
Some topics we will touch upon include– a general technique towards rounding SDP hierarchies, with application to subexponential time algorithm for unique games or a related problem. This general technique has found applications to other approximation problems such as MaxBisection. The talk will explore recent work on relations between SDP hierarchies and the spectrum of the input graph and their applications to algorithms and lower bounds. We will also show why algorithms of this general type must indeed take (almost) subexponential time for unique games, and discuss how sum-of-squares type arguments might help to go beyond these limitations.
Title: Algorithms for Semi-random instances of Unique Games
Speaker: Konstantin Makarychev (Microsoft Research)
Abstract: Many combinatorial optimization problems are much simpler in practice than in the worst-case. One of the challenges in the area of approximation algorithms is to explain this phenomena and to design algorithms that work well in real-life. In this lecture, we will discuss one of the models of real-life instances – the semi-random model, which was originally introduced by Blum and Spencer for the k coloring problem. I will present a new semi-random model for Unique Games and show that semi-random instances of Unique Games are "easy" i.e., there exists an approximation algorithm that given a (1-epsilon)-satisfiable unique game, returns a solution satisfying at least a half of all constraints. This result suggests that other problems may be not as hard in the semi-random case as in the worst-case. I will mention how to obtain constant factor approximation algorithms for semi-random graph partitioning problems (such as balanced cut, multicut, and small set expansion) and some other classical combinatorial optimization problems. Based on joint works with Alexandra Kolla (UIUC), Yury Makarychev (TTIC), Aravindan Vijayaraghavan (Princeton)