Rajsekar Manokaran: Hypercontractivity, Sum-of-Squares Proofs, and their Applications

Lunch is served at 12:00 noon (register at doodle.com/terp4ffhxhnnx6ru ). The presentation starts at *12:10* *pm* (note the time) and ends at 1 pm. Those of us who wish reconvene at 1:10 pm for ca two hours of more technical discussions.

Abstract

In this talk, I will present the recent work of Barak, Brandao, Harrow, Kelner, Steurer and Zhou on using the "Sum of Squares" semi-definite programming hierarchy in solving the known hard instances of Unique Games (UG) problem. The supposed hardness of this problem, known as the UG Conjecture has been instrumental in proving a wide variety of tight inapproximability results, hence warranting their study. [BBHKSZ '12] show that the SoS SDP hierarchy can be used to refute the conjecture on instances involving a noise operator on the boolean cube (which has been the basis of hard instances to this problem till date).

I will first describe the "2 to 4 norm" problem, showing how it relates to the UG conjecture, with a focus on the known family of hard instances. Then, I will describe the SDP hierarchy followed by an overview of the proof that the SDP does indeed refute the conjecture on this family of instances. I will leave the details of the proofs to the session after the seminar.