{"id":"openai-math/Parity-lifts-and-bounded-treewidth-witnesses-for-Weisfeiler-Leman-equivalence","pdf":"https://github.com/openai/math/blob/main/preprints/Parity-lifts-and-bounded-treewidth-witnesses-for-Weisfeiler-Leman-equivalence-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Parity-lifts-and-bounded-treewidth-witnesses-for-Weisfeiler-Leman-equivalence-September-25-2026","tags":["computational-complexity","weisfeiler-leman","graph-isomorphism"],"score":0,"title":"Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalence","domain":"Theoretical computer science","family":"133","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"For k ≥ 4, we construct two uncolored graphs that are k -dimensional Weisfeiler–Leman equivalent exactly when a prescribed finite-domain choice system has no compatible choice. The system has $`k+1`$ domains for joint refinement and k for separate-coordinate refinement. A successful choice is detected after two joint rounds or one separate round. Applied to sparse satisfiability, the reduction gives fixed-dimension $`n^{\\Omega(k)}`$ time exclusions under positive-rate ETH, even for deciding equality of these early histograms.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":false,"family_title":"The computational complexity of Weisfeiler–Leman refinement"}