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