50 citations · 210 across the 29 of their papers we have counts for
5 papers · 1 filter
Sherali--Adams Strikes Back
Ryan O'Donnell, Tselil Schramm
Let be any -vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by (for example, a random graph of average degree~…
SOS lower bounds with hard constraints: think global, act local
Pravesh Kothari, Ryan O'Donnell, Tselil Schramm
Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficiencies related to global constraints. First, they were not able to support a "cardinality constraint", as in,…
High-dimensional estimation via sum-of-squares proofs
Prasad Raghavendra, Tselil Schramm, David Steurer
Estimation is the computational task of recovering a hidden parameter associated with a distribution , given a measurement sampled from the distribution. High dimensio…
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
Boaz Barak, Chi-Ning Chou, Zhixian Lei +2
We give a quasipolynomial time algorithm for the graph matching problem (also known as noisy or robust graph isomorphism) on correlated random graphs. Specifically, for every …
The threshold for SDP-refutation of random regular NAE-3SAT
Yash Deshpande, Andrea Montanari, Ryan O'Donnell +2
Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has the property that spectral/SDP algorithms can efficiently refute random instances when the constraint density…