{"id":"arxiv/2610.23775","url":"https://arxiv.org/abs/2610.23775","tags":["cs.DS","math.OC","math.PR"],"score":0,"title":"Polytope Sampling at the Speed of Isoperimetry","domain":"cs.DS","source":"arxiv","authors":["Anming Gu","Bobby Shi","Kevin Tian","Hubert Yang"],"reviews":0,"subject":"cs.DS","summary":"We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with $m$ constraints in $n$ dimensions, uses $m \\cdot \\mathrm{poly}\\log(\\frac m δ)$ iterations, each running in time $O(mn^{ω- 1})$, to return a sample within total variation distance $δ$ to the uniform distribution. When $m =O(n)$ and $δ= \\mathrm{poly}(\\frac 1 n)$, our runtime improves upon all prior works by an $Ω(n^{2/3})$ factor. Our sampler is based on the recent \\emph{functional stochastic localization} framework of [GST26], and achieves…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-16","reactions":{}}