{"id":"arxiv/2606.00292","url":"https://arxiv.org/abs/2606.00292","tags":["cs.DS","cs.CC","math.CO","math.PR"],"score":0,"title":"High-Dimensional Expanders, the Sparsest Cut Problem, and Steurer's Conjecture","domain":"cs.DS","source":"arxiv","authors":["Farzam Ebrahimnejad","Shayan Oveis Gharan"],"reviews":0,"subject":"cs.DS","summary":"In 2010, Steurer conjectured that any family of $n$ unit-norm vectors $v_1,\\dots,v_n$ with polynomially small average correlation $\\mathbb{E}_{i,j}|\\langle v_i,v_j\\rangle|\\leq n^{-ε}$ contains linear-sized constant-separated sets. We refute this conjecture in a strong sense using the machinery of sparse high-dimensional expanders: such vector families do not even have linear-sized $\\frac{1}{\\log^{1/4-o(1)}(n)}$-separated sets. Consequently, we show that there are families of vertex expanders on $n$ vertices for which the (average) $L_2$-mixing time to the uniform distribution of any…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-29","reactions":{}}