7 papers
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 hypothe…
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…
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…