49 citations · 97 across the 8 of their papers we have counts for
3 papers · 1 filter
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification
Antares Chen, Jonathan Shi, Luca Trevisan
We prove that a random -regular graph, with high probability, is a cut sparsifier of the clique with approximation error at most $\left(2\sqrt{\frac 2 π} + o_{n,d}(1)\right)/\sq…
Polynomial-time Tensor Decompositions with Sum-of-Squares
Tengyu Ma, Jonathan Shi, David Steurer
We give new algorithms based on the sum-of-squares method for tensor decomposition. Our results improve the best known running times from quasi-polynomial to polynomial for several…
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi +1
We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a…