
Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree4 SOS
In this paper we show that simple semidefinite programs inspired by degr...
read it

Machinery for Proving SumofSquares Lower Bounds on Certification Problems
In this paper, we construct general machinery for proving SumofSquares...
read it

On the Mysteries of MAX NAESAT
MAX NAESAT is a natural optimization problem, closely related to its be...
read it

SumofSquares Lower Bounds for SherringtonKirkpatrick via Planted Affine Planes
The SumofSquares (SoS) hierarchy is a semidefinite programming metaa...
read it

The Spectrum of the Singular Values of ZShaped Graph Matrices
Graph matrices are a type of matrix which appears when analyzing the sum...
read it

On the Approximability of Presidential Type Predicates
Given a predicate P: {1, 1}^k →{1, 1}, let CSP(P) be the set of constr...
read it

Sum of squares bounds for the total ordering principle
In this paper, we analyze the sum of squares hierarchy (SOS) on the tota...
read it

On the Approximation Resistance of Balanced Linear Threshold Functions
In this paper, we show that there exists a balanced linear threshold fun...
read it

Lengths of Words Accepted by Nondeterministic Finite Automata
We consider two natural problems about nondeterministic finite automata....
read it

Sum of squares lower bounds from symmetry and a good story
In this paper, we develop machinery for proving sum of squares lower bou...
read it

The power of sumofsquares for detecting hidden structures
We study planted problemsfinding hidden structures in random noisy in...
read it

A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation
In this paper, we investigate property testing whether or not a degree d...
read it

Exact tensor completion with sumofsquares
We obtain the first polynomialtime algorithm for exact tensor completio...
read it
Aaron Potechin
is this you? claim profile