The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


             Walmart Lecture Series in Cryptography and Complexity

                    Seminar Room, Room 261, Ziskind Building
                          on Monday, December 13, 2010
                                    at 14:30


           Joint Walmart and Foundations of Computer Science Seminars


                                 David Steurer
                         Microsoft Research New England


                                 will speak on


                      Graph Expansion and Two-Prover Games

Abstract:
In a seminal paper, Khot proposed two conjectures about the approximability of
two-prover games, the Unique Games Conjecture and the d-to-1 Conjecture. A
sequence of later works showed that these conjectures imply strong and often
optimal approximation hardness results for many basic problems, making these
conjectures central open questions in approximation complexity.

I will discuss some recent results relating the approximability of two-prover
games and graph expansion, and shedding new light on the status of Khot's
conjectures.

On the one hand, we propose the Small-Set Expansion Hypothesis, a natural
assumption about the hardness of approximating the expansion of small sets in
graphs.  We show that this hypothesis implies the Unique Games Conjecture.  In
fact, the hypothesis turns out to be equivalent to a variant of this
conjecture. Furthermore, the Small-Set Expansion Hypothesis implies the first
strong approximation hardness results for several basic graph partitioning
problems like Balanced Separator.

On the other hand, we give subexponential algorithms for unique two-prover
games and, more generally, for d-to-1 two-prover games. These algorithms imply
that an NP-hardness reduction proving one of Khot's conjectures cannot have
fixed polynomial degree (unless SAT has subexponential algorithms).  At the
heart of these algorithms are new techniques for approximating the expansion of
small sets in graphs, giving further evidence for the close connection between
graph expansion and two-prover games.

This talk is based on joint works with (different subsets of) Sanjeev Arora,
Boaz Barak, Prasad Raghavendra, and Madhur Tulsiani.