130 citations · 209 across the 59 of their papers we have counts for
8 papers · 1 filter
Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
Leo Zhou, Noah Shutty, Mark Sellke +1
We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum…
Algorithmic threshold for high-dimensional projection pursuit I: general theory
Brice Huang, Mark Sellke, Nike Sun
We study a null model of high-dimensional projection pursuit: we are given points sampled i.i.d. from a standard gaussian in dimensions, where with $M/N\toα\…
Thompson Sampling Is 2-Competitive for Mistakes
Mark Sellke, Gregory Valiant
We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our an…
A Counterexample to the Gaussian Completely Monotone Conjecture
Yuzhou Gu, Mark Sellke
We provide an explicit probability measure on for which the fifth time derivative of the entropy along the heat flow is positive at some time. This disproves the Gauss…
Short proofs in combinatorics, probability and number theory II
Boris Alexeev, Moe Putterman, Mehtaab Sawhney +2
We give a quintet of proofs resulting from questions posed by Erdős. These questions concern ordinary lines in planar point sets, sequences with uniformly small exponential sums, $…
Short proofs in combinatorics and number theory
Boris Alexeev, Moe Putterman, Mehtaab Sawhney +2
We give a triplet of short proofs, each of which answers a question raised by Erdős. The first concerns the small prime factors of , the second concerns whether an ad…
Stable algorithms cannot reliably find isolated perceptron solutions
Shuyang Gong, Brice Huang, Shuangping Li +1
We study the binary perceptron, a random constraint satisfaction problem that asks to find a Boolean vector in the intersection of independently chosen random halfspaces. A strikin…
On Anti-Confinement Estimates for Self-Repelling Random Walks
Tobias Schmidt, Mark Sellke
We study a class of -dimensional random walks, including the two-dimensional simple random walk, reweighted by a self-repelling Gibbsian pair potential. We prove lower bounds on…