Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalence
Source: github.com/openai/math/tree/main/preprints/Parity-lifts-and…
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.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/Parity-lifts-and-bounded-treewidth-witnesses-for-Weisfeiler-Leman-equivalence
curl -X POST /api/v1/records/openai-math/Parity-lifts-and-bounded-treewidth-witnesses-for-Weisfeiler-Leman-equivalence/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Parity-lifts-and-bounded-treewidth-witnesses-for-Weisfeiler-Leman-equivalence/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…