{"id":"openai-math/Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut","pdf":"https://github.com/openai/math/blob/main/preprints/Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-September-24-2026/Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-September-24-2026.pdf","url":"https://github.com/openai/math/tree/main/preprints/Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-September-24-2026","tags":["theoretical-cs","approximation-algorithms","sparsest-cut"],"score":0,"title":"Near-square-root logarithmic integrality gaps for uniform sparsest cut","domain":"Theoretical computer science","family":"117","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We construct uniform sparsest-cut instances whose Goemans–Linial semidefinite integrality gap is at least $`c\\sqrt{\\log n}/(\\log\\log n)^3`$ along a sequence $`n\\to\\infty`$. The demand is one between every pair of distinct vertices, and the capacities are nonnegative real numbers. This matches the Arora–Rao–Vazirani upper bound up to a power of $`\\log\\log n`$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":true,"family_title":"Uniform sparsest cut: hardness and semidefinite gaps"}