17 citations · 18 across the 3 of their papers we have counts for
3 papers
math.OC2017★ 1 cited
Exponential lower bounds on spectrahedral representations of hyperbolicity cones
Prasad Raghavendra, Nick Ryder, Nikhil Srivastava +1
The Generalized Lax Conjecture asks whether every hyperbolicity cone is a section of a semidefinite cone of sufficiently high dimension. We prove that the space of hyperbolicity co…
cs.CC2017★ 17 cited
On the Bit Complexity of Sum-of-Squares Proofs
Prasad Raghavendra, Benjamin Weitz
It has often been claimed in recent papers that one can find a degree d Sum-of-Squares proof if one exists via the Ellipsoid algorithm. In [O17], Ryan O'Donnell notes this widely q…
cs.DM2011
An Improvement on Ranks of Explicit Tensors
Benjamin Weitz
We give constructions of n^k x n^k x n tensors of rank at least 2n^k - O(n^(k-1)). As a corollary we obtain an [n]^r shaped tensor with rank at least 2n^(r/2) - O(n^(r/2)-1) when r…