50 citations · 210 across the 29 of their papers we have counts for
3 papers · 1 filter
Computing exact minimum cuts without knowing the graph
Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg
We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimiza…
The power of sum-of-squares for detecting hidden structures
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin +3
We study planted problems---finding hidden structures in random noisy inputs---through the lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of power…
Fast and robust tensor decomposition with applications to dictionary learning
Tselil Schramm, David Steurer
We develop fast spectral algorithms for tensor decomposition that match the robustness guarantees of the best known polynomial-time algorithms for this problem based on the sum-of-…