21 citations · 61 across the 21 of their papers we have counts for
4 papers · 1 filter
Near-optimal fitting of ellipsoids to random points
Aaron Potechin, Paxton Turner, Prayaag Venkat +1
Given independent standard Gaussian points in dimension , for what values of does there exist with high probability an origin-symmetric ellipsoid tha…
Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
Bohdan Kivva, Aaron Potechin
In this paper we show that simple semidefinite programs inspired by degree SOS can exactly solve the tensor nuclear norm, tensor decomposition, and tensor completion problems o…
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…
Improved upper and lower bound techniques for monotone switching networks for directed connectivity
Aaron Potechin
In this paper, we analyze the monotone space of complexity of directed connectivity for a large class of input graphs using the switching network model. The upper and lower bou…