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 >>>

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. ... more >>>

We prove an unconditional lower bound that any linear program that achieves an $O(n^{1-\epsilon})$ approximation for clique has size $2^{\Omega(n^\epsilon)}$. There has been considerable recent interest in proving unconditional lower bounds against any linear program. Fiorini et al proved that there is no polynomial sized linear program for traveling salesman. ... more >>>

Here, we give an algorithm for deciding if the nonnegative rank of a matrix $M$ of dimension $m \times n$ is at most $r$ which runs in time $(nm)^{O(r^2)}$. This is the first exact algorithm that runs in time singly-exponential in $r$. This algorithm (and earlier algorithms) are built on ... more >>>

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct ... more >>>