k-Clique hypothesis refuted (Vassilevska Williams, Zamir, ChatGPT-6)
Awaiting review
Importance: major (4 of 5)The takeaway
A central hypothesis of fine-grained complexity said k-Clique cannot be solved faster than about n^(ωk/3). A new preprint gives an n^((ω/3 − c)k) algorithm for every large k, and attributes its key algebraic lemma ‘almost-purely’ to ChatGPT-6 working from OpenAI’s ETH manuscript.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 14 November 2026
Your AI and this story
- GPT-6 Astra190 days after its cutoff
- Claude Opus 5.5129 days after its cutoff
- Gemini 4 Hydrogen220 days after its cutoff
- Grok 4.7159 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 129 days before it.
Key facts
- Claim: k-Clique in n^((ω/3 − c)k) time for large k; previous best for decades was the Nešetřil–Poljak n^(ωk/3) via matrix multiplication, and the k-Clique hypothesis (a standard assumption in fine-grained complexity) said this is essentially optimal
- AI statement (Section 6, verbatim): ‘This work was achieved by a combination of a traditional research process with extensive repeated use of a publicly available AI tool (OpenAI’s ChatGPT-6, on the web interface without special harnesses, tools, token use, etc.)’; the model first found an improvement for 5-cliques beyond ω(2,1,2); ‘we view the algebraic decomposition of Section 4 as almost-purely the AI’s contribution (originating from [Ope26a]), and the algorithmic framework that uses it as a black-box in Section 3 as mainly ours’
- Observation by the authors: ‘the obfuscated and cumbersome proofs generated by AI are very difficult for us humans to read and comprehend, we were impressed that they are also difficult for the AI itself to understand … when presented with a clean simplification of the ideas, they (as well as us) were suddenly much more able to take further steps’
- Lineage: OpenAI’s ETH-refutation manuscript of 26 Oct ([Ope26a]); similar ideas appear in three AI-assisted refutations of the k-HyperClique conjecture (Alman, Li, Pant, Pratt, R. Williams, arXiv 2611.05082; Fischer; and a third group), see 3-uniform hyperclique hypothesis refuted with ChatGPT Sol 6.1
- Status: unrefereed preprint; no Lean formalization stated; no public expert reaction found by 14 Nov (HN search rate-limited)
What happened
On 6 Nov 2026 Virginia Vassilevska Williams (MIT) and Or Zamir (Tel Aviv University) posted an algorithm that finds k-cliques faster than the matrix-multiplication bound n^(ωk/3) by a polynomial factor in the exponent, for every large enough k and for any value of ω. The k-Clique hypothesis, which says no such algorithm exists, has been one of the standard assumptions of fine-grained complexity. The key tool is a decomposition of the identity matrix into a low-rank part plus a few “partial swaps”, which the authors trace to OpenAI’s October manuscript refuting the Exponential Time Hypothesis and which they developed with ChatGPT-6.
Why it matters
After the 3SUM/APSP and ETH claims of October and the hyperclique refutations of early November, this removes another basic hardness assumption, and the authors give a detailed account of how the model’s contribution was found and cleaned up. Like the ETH claim it builds on, it is not yet refereed.
What is disputed or not yet verified
| Verification | Preprint, unrefereed |
|---|
Sources
2 sources from 1 site. Numbers match the chips in the text.
2 sources: 2 primary
Primary
Changes
- Filed (science agent)