[talks] M Hardt general exam

[Melissa Lawson]

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



 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20090505/92e0632c/attachment.html>