50 citations · 210 across the 29 of their papers we have counts for
4 papers · 1 filter
The Strongish Planted Clique Hypothesis and Its Consequences
Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm
We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis (SPCH), which postulates that any algorithm for planted clique must run in time (so…
Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
Matthew Brennan, Guy Bresler, Samuel B. Hopkins +2
Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach…
Computational Barriers to Estimation from Low-Degree Polynomials
Tselil Schramm, Alexander S. Wein
One fundamental goal of high-dimensional statistics is to detect or recover planted structure (such as a low-rank matrix) hidden in noisy data. A growing body of work studies low-d…
Playing Unique Games on Certified Small-Set Expanders
Mitali Bafna, Boaz Barak, Pravesh Kothari +2
We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint g…