Title: Approximability and Proof Complexity

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 and Max-Cut poroblems. We show that constant rounds
of Lasserre hierarchy certify the optimal value of Balanced-Seperator
instances, and gives better-than-0.878 approximation to the Max-Cut
instances.

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