Moritz Hardt will present his research seminar/general exam on Monday May 11 at 2PM in Room 302 (note room). The members of his committee are: Boaz Barak, advisor, Sanjeev Arora, 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. -------------------------------------------------- I. Title + abstract What are plausible hard instances for Unique Games? Unique Games are a family of constraint satisfaction problems conjectured to be NP-hard. This conjecture due to Khot implies that simple semidefinite programs (SDP) achieve optimal approximation ratios for several important problems including Max-Cut and Vertex Cover. Unfortunately, little evidence in support of the conjecture exists. Indeed, random instances of Unique Games are known to be easy. In this work we thus address the question: What are plausible hard instances for Unique Games? Our approach is to consider the refutation problem induced by subsampling a given SDP gap instance to constant degree. While subsampling preserves global parameters such as the integrality gap, the lack of local structure may lead to computational hardness. In support of our methodology, we observe that a constant degree subsample of essentially any unsatisfiable k-CSP instance gives rise to strong lower bounds in the Lasserre SDP hierarchy so long as k is greater than 3. Based on the work of Charikar, Makarychev and Makarychev, we also show that for 2-CSPs and Unique Games a constant degree subsample of any unsatisfiable instance gives strong lower bounds in the Sherali-Adams linear programming hierarchy. Unfortunately, our approach can only go so far. Appealing to Grothendieck's inequality, we show that for any 2-CSP the induced refutation problem is solvable in polynomial time. We then consider the question whether known SDP gaps withstand additional constraints when subsampled to constant degree. Somewhat surprisingly, we can show that already the triangle inequalities annihilate the integrality gap of the well known Feige-Schechtman gap instance for Max-Cut. This remains true even in a constant degree subsample. As for a future research direction, similar ideas could apply to all known Unique Games gap instances. My talk is based on ongoing research with Boaz Barak, Thomas Holenstein and David Steurer. II. Reading list Books: * Arora, Barak. Computational Complexity. Chapters 11,13,14,18--23 Papers: [Ale03] Alekhnovich. More on average case vs approximation complexity [ABW09] Applebaum, Barak, Wigderson. Public Key Cryptography from Different Assumptions [AKK+08] Arora, Khot, Kolla, Steurer, Tulsiani and Vishnoi. Unique Games on Expanding Constraint Graphs are Easy [CMM09] Charikar, Makarychev, Makarychev. Integrality Gaps for Sherali- Adams Relaxations [Fei02] Feige. Relations between Average Case Complexity and Approximation Complexity [FS02] Feige and Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT [Hol07] Holenstein. Parallel Repetition: Simplifications and the no-signaling case [KKMO04] Khot, Kindler, Mossel, O'Donnell. Optimal inapproximability results for max-cut and other 2-variable CSPs? [KV05] Khot, Vishnoi. The unique games conjecture, integrality gap for cut problems, and embeddability of negative type metrics into l1. [Rag08] Raghavendra. Optimal Algorithms and Inapproximability Results for Every CSP? [Sch08] Schoenebeck. Linear Level Lasserre Lower Bounds for Certain k-CSPs [TTV09] Trevisan, Tulsiani, Vadhan. Regularity, Boosting, and Efficiently