We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly ... more >>>

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.
Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ... more >>>

We prove that with high probability over the choice of a random graph G from the Erd\H{o}s-R\'enyi distribution G(n,1/2), the n^{O(d)}-time degree d Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least n^{1/2-c(d/\log n)^{1/2}} for some constant c>0.
This yields a nearly tight ... more >>>

Suppose we want to minimize a polynomial p(x) = p(x_1, \dots, x_n), subject to some polynomial constraints q_1(x), \dots, q_m(x) \geq 0, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include x_i^2 \leq 1 for all $1 \leq i \leq ... more >>>

For every constant \epsilon>0, we give an \exp(\tilde{O}(\sqrt{n}))-time algorithm for the 1 vs 1-\epsilon Best Separable State (BSS) problem of distinguishing, given an n^2\times n^2 matrix M corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state \rho that M accepts with probability 1, ... more >>>

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>>

One of the major open problems in proof complexity is to prove lower bounds on AC_0[p]-Frege proof
systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove
lower bounds on the size for Polynomial Calculus over the \{\pm 1\} basis. In this ... more >>>

We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time.
Our construction is based on the high-dimensional expanders devised by Lubotzky, ... more >>>

We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function f: \{0,1\}^n \rightarrow \{0,1\}, SoS requires degree \Omega(s^{1-\epsilon}) to prove that f does not have circuits of size s (for any s > \text{poly}(n)). ... more >>>