arxivcs.DScs.LGmath.OC2026-07-15
Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes
Inspired by interior-point methods (IPM) for structured convex optimization, Kannan and Narayanan introduced the Dikin walk for sampling uniformly from polytopes in 2009. As in IPMs, the Dikin walk is affine-invariant, and its convergence is governed by the barrier geometry used…