[talks] D Steurer general exam
Melissa M Lawson
mml at CS.Princeton.EDU
Fri Jan 11 14:57:55 EST 2008
David Steurer will present his research seminar/general exam on Friday January 18
at 2PM in Room 402. The members of his committee are: Sanjeev Arora (advisor),
Moses Charikar, and Bernard Chazelle. Everyone is invited to attend his talk, and
those faculty wishing to remain for the oral exam following are welcome to do so.
His abstract and reading list follow below.
Unique Games with Expanding Constraints Graphs are Easy
We consider the following constraint satisfaction problem: Given an over-determined system
of linear equations modulo a prime number k, where each equations depends only on two
variables, we want to find a solution that satisfies as many of the equations as possible.
Khot's Unique Games Conjecture asserts that this problem is hard to approximate even if
almost all equations can be satisfied. Proven true, the conjecture would imply that
current algorithmic techniques are optimal for many combinatorial optimization problems,
in particular, Maximum Cut and Vertex Cover.
By some researchers, it has also been conjectured that the problem remains hard to
approximate even if the constraint graph of the instance has significant expansion. This
conjecture would have implied strong inapproximability results for the notorious Sparset
In this talk, I will present an approximation algorithm that refutes the latter
conjecture. Our algorithm is based on a novel analysis of a well-known semidefinite
programming relaxation. Our analysis also leads to a strong parallel repetition theorem
for unique games when the constraint graph is an expander.
The presented results are based on joint work with Sanjeev Arora, Subhash Khot, Alex
Kolla, Madhur Tulsiani, and Nisheeth Vishnoi.
books / survey articles:
- Kleinberg, Tardos. Algorithm Design.
- Boyd, Vandenberghe. Convex Optimization.
- Lovasz. Semidefinite programs and combinatorial optimization.
- Hoory, Linial, Wigderson. Expander graphs and their
applications. (Chapters 2,4,7)
- Arora, Barak. Complexity Theory: A Modern Approach.
(PCP Chapters, 18 & 19)
- Lovasz. On the Shannon capacity of a graph.
- Feige, Lovasz. Two-prover one-round proof systems, their power and
- Goemans, Williamson. Improved Approximation Algorithms for Maximum
Cut and Satisfiability Problems Using Semidefinite Programming.
- Karger, Motwani, Sudan. Approximate Graph Coloring by Semidefinite
- Alon, Naor. Approximating the Cut-Norm via Grothendieck's
- Trevisan. Approximation algorithms for unique games.
- Charikar, Makarychev, Makarychev. Near-optimal algorithms for
- Chlamtac, Makarychev, Makarychev. How to Play Unique Games Using
- Khot. On the power of unique 2-prover 1-round games.
- Khot, Kindler, Mossel, O'Donnell. Optimal inapproximability results
for max-cut and other 2-variable CSPs?
- Khot, Vishnoi. The unique games conjecture, integrality gap for cut
problems, and embeddability of negative type metrics into l1.
More information about the talks