50 citations · 210 across the 29 of their papers we have counts for
39 papers
Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part I: Glauber Dynamics
Aniket Das, Tselil Schramm
In the tensor principal components analysis (tensor PCA) problem, we are asked to recover an unknown vector in from a noisy observation of its -th tensor power, for…
Algorithms for adaptive and heteroskedastic linear regression at the computational threshold
Spencer Compton, Tselil Schramm
We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic l…
High-Dimensional Procrustes Matching via Tree Counts
Xiaochun Niu, Tselil Schramm, Jiaming Xu
Suppose we observe two sets of Gaussian vectors in , with the promise that, after applying a permutation of and a rotation of , the two sets a…
Easy, robust approximate message passing for planted spike models
Misha Ivkov, Tselil Schramm
We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let be a sufficiently small cons…
The statistical threshold for planted matchings and spanning trees
Louigi Addario-Berry, Omer Angel, Gábor Lugosi +2
In this paper, we study the problem of detecting the presence of a planted perfect matching or spanning tree in an Erdős--Rényi random graph. More precisely, we study the hypothesi…
Polynomial-time sampling despite disorder chaos
Eric Ma, Tselil Schramm
A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes th…
Fast, robust approximate message passing
Misha Ivkov, Tselil Schramm
We give a fast, spectral procedure for implementing approximate-message passing (AMP) algorithms robustly. For any quadratic optimization problem over symmetric matrices with i…
Some easy optimization problems have the overlap-gap property
Shuangping Li, Tselil Schramm
We show that the shortest - path problem has the overlap-gap property in (i) sparse graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Fu…
Discrepancy Algorithms for the Binary Perceptron
Shuangping Li, Tselil Schramm, Kangjie Zhou
The binary perceptron problem asks us to find a sign vector in the intersection of independently chosen random halfspaces with intercept . We analyze the performance of the can…
Semidefinite programs simulate approximate message passing robustly
Misha Ivkov, Tselil Schramm
Approximate message passing (AMP) is a family of iterative algorithms that generalize matrix power iteration. AMP algorithms are known to optimally solve many average-case optimiza…
Spectral clustering in the Gaussian mixture block model
Shuangping Li, Tselil Schramm
Gaussian mixture block models are distributions over graphs that strive to model modern networks: to generate a graph from such a model, we associate each vertex with a latent…
Local and global expansion in random geometric graphs
Siqi Liu, Sidhanth Mohanty, Tselil Schramm +1
Consider a random geometric 2-dimensional simplicial complex sampled as follows: first, sample vectors uniformly at random on $\m…
The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins +3
Many high-dimensional statistical inference problems are believed to possess inherent computational hardness. Various frameworks have been proposed to give rigorous evidence for su…
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…
Testing thresholds for high-dimensional sparse random geometric graphs
Siqi Liu, Sidhanth Mohanty, Tselil Schramm +1
In the random geometric graph model , we identify each of our vertices with an independently and uniformly sampled vector from the -dimensional unit sph…
The SDP value of random 2CSPs
Amulya Musipatla, Ryan O'Donnell, Tselil Schramm +1
We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over~. For each model , we identify…
Robust Regression Revisited: Acceleration and Improved Estimation Rates
Arun Jambulapati, Jerry Li, Tselil Schramm +1
We study fast algorithms for statistical regression problems under the strong contamination model, where the goal is to approximately optimize a generalized linear model (GLM) give…
Non-asymptotic approximations of neural networks by Gaussian processes
Ronen Eldan, Dan Mikulincer, Tselil Schramm
We study the extent to which wide neural networks may be approximated by Gaussian processes when initialized with random weights. It is a well-established fact that as the width of…
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…
Subexponential LPs Approximate Max-Cut
Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
We show that for every , the degree- Sherali-Adams linear program (with variables and constraints) approximates the…
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~…