Title: Approximability and Proof Complexity

Speaker: Yuan Zhou, CMU

Time/Date:  Friday, Mar 8, 11-12
Location: Room 3501

Abstract:

We study the connection between approximability of constraint
satisfaction problems (CSPs) and algebraic proof systems. We work on
the ``Sum-of-Squares (SOS) proof system'' introduced by Grigoriev and
Vorobjov, where we show that degree-$d$ SOS proofs give upper bounds
on the value of the $Theta(d)$-rounds Lasserre SDP relaxation. Using
this fact, we consider the strong integrality gap instances known for
the notorious Unique-Games CSP and show that degree-8 SOS proofs can
certify the instances have value close to 0. Thus the constant-round
Lasserre SDP relaxation algorithm refutes their having optimal value.
This is in contrast of the fact that these instances still have value
near 1 after $\exp((\log \log n)^{\Omega(1)})$ rounds of the rather
powerful Sherali-Adams+SDP hierarchy.

We also consider the known integrality gap instances (for
superconstant rounds of Sherali-Adams+SDP hierarchy) for the
Balanced-Seperator, Max-Cut, and Vertex-Cover problems. We show that
constant rounds of Lasserre hierarchy certify the optimal value of
Balanced-Seperator instances, gives better-than-0.878 approximation to
the Max-Cut instances, and solves ``all but the hardest'' instances
for Vertex-Cover.

This is based on joint works with Boaz Barak, Fernando Brandao, Aram
Harrow, Manuel Kauers, Jonathan Kelner, Ryan O'Donnell, David Steurer,
and Li-Yang Tan.

----

Yuan Zhou received his Bachelor's degree in Computer Science from
Tsinghua University in 2009, where he attended the Special Pilot CS
Class supervised by Turing Award laureate Prof. Andrew Yao. Yuan is
currently a graduate student at Carnegie Mellon University, working on
theoretical computer science with Prof. Venkatesan Guruswami and Prof.
Ryan O'Donnell. His research interests focus on approximability of
fundamental optimization problems. He is also interested in
algorithmic mechanism design, algebraic dichotomy theory, coding
theory, and their relations to the theory of approximations.