21 citations · 61 across the 21 of their papers we have counts for
4 papers · 1 filter
Sum of squares lower bounds from symmetry and a good story
Aaron Potechin
In this paper, we develop machinery which makes it much easier to prove sum of squares lower bounds when the problem is symmetric under permutations of and the unsatisfiabi…
The power of sum-of-squares for detecting hidden structures
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin +3
We study planted problems---finding hidden structures in random noisy inputs---through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of power…
A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation
Aaron Potechin, Liu Yang
In this paper, we investigate property testing whether or not a degree d multivariate poly- nomial is a sum of squares or is far from a sum of squares. We show that if we require t…
Exact tensor completion with sum-of-squares
Aaron Potechin, David Steurer
We obtain the first polynomial-time algorithm for exact tensor completion that improves over the bound implied by reduction to matrix completion. The algorithm recovers an unknown…