14 citations · 38 across the 13 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2025
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…
cs.CC2024
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…
cs.CC2020
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…