50 citations · 210 across the 29 of their papers we have counts for
4 papers · 1 filter
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…
Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program
Prasad Raghavendra, Tselil Schramm
We give a lower bound of for the degree-4 Sum-of-Squares SDP relaxation for the planted clique problem. Specifically, we show that on an Erdös-Rényi graph $G(n,…
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…
Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
Ronen Eldan, Miklós Rácz, Tselil Schramm
We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, pe…