[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
Cut problem.

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)

research articles:

 - Lovasz. On the Shannon capacity of a graph.

 - Feige, Lovasz. Two-prover one-round proof systems, their power and
   their problems.

 - Goemans, Williamson. Improved Approximation Algorithms for Maximum
   Cut and Satisfiability Problems Using Semidefinite Programming.

 - Karger, Motwani, Sudan. Approximate Graph Coloring by Semidefinite
   Programming.

 - Alon, Naor. Approximating the Cut-Norm via Grothendieck's
   Inequality.

 - Trevisan. Approximation algorithms for unique games.

 - Charikar, Makarychev, Makarychev. Near-optimal algorithms for
   unique games.

 - Chlamtac, Makarychev, Makarychev. How to Play Unique Games Using
   Embeddings.

 - 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 mailing list