{"id":"openai-math/Constant-factor-hardness-of-uniform-sparsest-cut","pdf":"https://github.com/openai/math/blob/main/preprints/Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026/Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026.pdf","url":"https://github.com/openai/math/tree/main/preprints/Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026","tags":["computational-complexity","approximation-algorithms","graph-theory"],"score":0,"title":"Constant-factor hardness of uniform sparsest cut","domain":"Theoretical computer science","family":"117","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We prove that, for every fixed C > 1, approximating Uniform Sparsest Cut within factor C is NP-hard. The output graphs have nonnegative rational capacities and unit demand between every pair of distinct vertices.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":false,"family_title":"Uniform sparsest cut: hardness and semidefinite gaps"}