38 citations · 56 across the 7 of their papers we have counts for
7 papers
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…
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…
Steiner Network Problems on Temporal Graphs
Alex Khodaverdian, Benjamin Weitz, Jimmy Wu +1
We introduce a temporal Steiner network problem in which a graph, as well as changes to its edges and/or vertices over a set of discrete times, are given as input; the goal is to f…
Symmetric Tensor Completion from Multilinear Entries and Learning Product Mixtures over the Hypercube
Tselil Schramm, Benjamin Weitz
We give an algorithm for completing an order- symmetric low-rank tensor from its multilinear entries in time roughly proportional to the number of tensor entries. We apply our t…
The matching problem has no small symmetric SDP
Gábor Braun, Jonah Brown-Cohen, Arefin Huq +5
Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvoß recently proved that any, not necessarily symmetric, linear program also has exp…
Computational Limits for Matrix Completion
Moritz Hardt, Raghu Meka, Prasad Raghavendra +1
Matrix Completion is the problem of recovering an unknown real-valued low-rank matrix from a subsample of its entries. Important recent results show that the problem can be solved…
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…