Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs
Source: github.com/openai/math/tree/main/preprints/Variable-dimensi…
Deciding joint-update k -dimensional Weisfeiler–Leman equivalence is $\mathsf{EXPTIME}$-complete when the two graphs are given by explicit adjacency matrices and k ≥ 2 is encoded in binary. The result holds even for connected simple uncolored graphs of equal positive order and maximum degree at most three.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/Variable-dimension-Weisfeiler-Leman-equivalence-on-general-and-subcubic-graphs
curl -X POST /api/v1/records/openai-math/Variable-dimension-Weisfeiler-Leman-equivalence-on-general-and-subcubic-graphs/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Variable-dimension-Weisfeiler-Leman-equivalence-on-general-and-subcubic-graphs/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
news | Tim Seppelttseppelt.github.ioTim Seppelt
the publication of the OpenAI papers yesterday, we have decided to put the current version of our paper Lower Bounds for Weisfeiler-Leman (with Radu Curticapean, Mingjun Liu, and Daniel Neuen) online. The results in the paper extend tight lower complexity lower bounds on the Weisfeiler-Leman…