Publications (7)
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…
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…
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…
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…