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.