{"id":"openai-math/Unconditional-time-lower-bounds-for-Weisfeiler-Leman-equivalence","pdf":"https://github.com/openai/math/blob/main/preprints/Unconditional-time-lower-bounds-for-Weisfeiler-Leman-equivalence-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Unconditional-time-lower-bounds-for-Weisfeiler-Leman-equivalence-September-25-2026","tags":["complexity-theory","graph-isomorphism","weisfeiler-leman"],"score":0,"title":"Unconditional time lower bounds 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 every sufficiently large fixed k , deciding whether two n -vertex graphs are k -Weisfeiler–Leman equivalent requires $`n^{\\Omega(k)}`$ deterministic sequential time in the worst case. The bound holds at every sufficiently large graph order, even for simple connected uncolored graphs of diameter at most two, without a complexity assumption. Inputs are explicit adjacency matrices; the models are multitape Turing machines and sequential logarithmic-word RAMs with fixed polynomial-bit-time instructions. Both joint and separate replacement conventions are covered.","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"}