VibeMathedMath problems solved with AI

The kk-Clique Hypothesis

Nesetril and Poljak (1985) reduced kk-Clique in nn-node graphs to triangle detection in O(nk/3)O(n^{k/3})-node graphs, giving an nωk/3+o(1)n^{\omega k/3+o(1)}-time algorithm for kk divisible by 3, where ω\omega is the exponent of square matrix multiplication. Woeginger (2004) challenged algorithm designers to beat this for some fixed kk, and Abboud, Backurs and Vassilevska Williams formulated the kk-Clique Hypothesis: in the word-RAM model with O(log⁡n)O(\log n)-bit words, for kk divisible by 3, detecting a kk-clique in an nn-node graph requires nωk/3−o(1)n^{\omega k/3-o(1)} time. Many fine-grained lower bounds rest on it. Is it true?

Result
Disproved(see note)
Status
Candidate (review pending)
AI contribution
AI-assisted
Method
Argument
Field
Fine-grained complexity
Posed by
Gerhard Woeginger (2004 open-problems survey) and Amir Abboud, Arturs Backurs and Virginia Vassilevska Williams (FOCS 2015; SIAM J. Comput. 2018), as cited by the manuscript
Year posed
2004
Years open
22y
Solved
2026-11-06
Model
ChatGPT-6
Vendor
OpenAI
Collaborators
Virginia Vassilevska Williams, Or Zamir
Verification
Unreviewed
Publication
Preprint
Significance
45 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there are constants K0K_0 and δ>0\delta>0, independent of ω≥2\omega\ge2, such that for every k≥K0k\ge K_0, kk-Clique (indeed weighted kk-clique counting) can be solved in O(n(ω−δ)k/3)O(n^{(\omega-\delta)k/3}) time. Because the saving is relative to the true ω\omega, it refutes the hypothesis whatever ω\omega is, even if ω=2\omega=2. The core is a faster algorithm for weighted 9-node pattern sums, lifted to large kk by the Nesetril-Poljak reduction. It is separate from the refutations of ETH, 3SUM and APSP catalogued here, none of which implies it; its Section 4 lemma is traced to the OpenAI ETH paper. K0K_0 and δ\delta are not optimized.

What the AI did

The paper's Section 6 says the work combined a traditional research process with extensive repeated use of ChatGPT-6 on the web interface. Starting from the authors' ideas for 5-cliques and the OpenAI ETH refutation as context, the model found a first improvement for 5-cliques; AI-assisted distillation then produced the algebraic decomposition of Section 4, which the authors view as almost purely the AI's contribution (originating from the OpenAI ETH paper), while the algorithmic framework of Section 3 is mainly theirs.

Verification

No independent mathematician has checked this yet. Checked here on 15 November 2026: the arXiv record 2611.09764 (6 Nov 2026, Vassilevska Williams and Zamir) and the PDF on Zamir's page (same title): abstract, introduction, Theorem 1.1, Section 6 (Reflection on Human-AI interaction) and references. The hypothesis as quoted in the paper, citing Woeginger 2004 and Abboud-Backurs-Vassilevska Williams, matches the statement; Theorem 1.1 for kk divisible by 3 and k≥K0k\ge K_0 contradicts it. The proofs of Sections 3 and 4 were not read or refereed here.

Sources

Submitted by MellowGander562 on

Changelog2 changes

Discussion