Pravesh Kothari: Sum of Squares Lower Bounds from Pairwise Independence

The Sum of Squares (SoS) Algorithm is a family of algorithms parametrized by a number d called the degree where the d^{th} algorithm takes n^{O(d)} time to execute. It can be seen as a common generalization and extension of both linear programming and spectral techniques and has been remarkably successful in combinatorial optimization capturing the state of the art algorithms for Sparsest Cut, Max-Cut, Unique Games/Small Set Expansion etc.

An instance of a constraint satisfaction problem consists of a predicate P:{0,1}^k --> {0,1}, n Boolean variables and a collection of ordered k-tuples C_1, C_2, ...,C_m on literals on the variables called as the constraints. The goal is to come up with an assignment for each variable so that P(C_i) = 1 for as many constraint C_i as possible. A predicate P is pairwise independent if there is a balanced pairwise independent probability distribution on its satisfying assignments. Such predicates are very abundant, in that a random predicate on k variables with ~ k^2 satisfying assignments is pairwise independent with high probability.

This talk focuses on showing that despite its remarkable success in combinatorial optimization, for constraint satisfaction problems on pairwise independent predicates, the SoS algorithm requires fully exponential time to outperform the simple algorithm that returns a random Boolean value for each variable x_i.

Specifically, there exists an instance I of Max-P CSPs on n variables where P is any pairwise independent predicate, such that no assignment can satisfy more than ~ |P^{-1}|/2^k fraction of the constraints of I but the SoS algorithm of Theta(n) degree cannot certify that I is unsatisfiable. Interestingly, it is not presently known whether all pairwise independent CSPs are NP-hard to approximate beyond the random assignmen t threshold.

I will start by discussing some background facts about the SoS algorithm and CSPs; the talk will be self-contained and will not require any special background.

This is based on joint work with Boaz Barak and Siu On Chan.