The -Clique Hypothesis
Nesetril and Poljak (1985) reduced -Clique in -node graphs to triangle detection in -node graphs, giving an -time algorithm for divisible by 3, where is the exponent of square matrix multiplication. Woeginger (2004) challenged algorithm designers to beat this for some fixed , and Abboud, Backurs and Vassilevska Williams formulated the -Clique Hypothesis: in the word-RAM model with -bit words, for divisible by 3, detecting a -clique in an -node graph requires 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 and , independent of , such that for every , -Clique (indeed weighted -clique counting) can be solved in time. Because the saving is relative to the true , it refutes the hypothesis whatever is, even if . The core is a faster algorithm for weighted 9-node pattern sums, lifted to large 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. and 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 divisible by 3 and contradicts it. The proofs of Sections 3 and 4 were not read or refereed here.
Sources
Submitted by MellowGander562 on