49 citations · 97 across the 8 of their papers we have counts for
9 papers
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu +1
We study random constraint satisfaction problems (CSPs) in the unsatisfiable regime. We relate the structure of near-optimal solutions for any Max-CSP to that for an associated spi…
A Robust Spectral Algorithm for Overcomplete Tensor Decomposition
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi
We give a spectral algorithm for decomposing overcomplete order-4 tensors, so long as their components satisfy an algebraic non-degeneracy condition that holds for nearly all (all…
Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond
Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu +1
We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph…
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…
Tensor principal component analysis via sum-of-squares proofs
Samuel B. Hopkins, Jonathan Shi, David Steurer
We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order- tensor of the form $T = τ\cdot v_0^{\oti…
Sparse Quantum Codes from Quantum Circuits
Dave Bacon, Steven T. Flammia, Aram W. Harrow +1
We describe a general method for turning quantum circuits into sparse quantum subsystem codes. The idea is to turn each circuit element into a set of low-weight gauge generators th…
Efficient Computation of the Kauffman Bracket
Lauren Ellenberg, Gabriella Newman, Stephen Sawin +1
This paper bounds the computational cost of computing the Kauffman bracket of a link in terms of the crossing number of that link. Specifically, it is shown that the image of a tan…