50 citations · 210 across the 29 of their papers we have counts for
5 papers · 1 filter
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…