Author verified Collaborative

Refutation of the k-Clique hypothesis, independent of the matrix multiplication exponent

Two complexity theorists working back and forth with ChatGPT-6 published an algorithm that counts weighted k-cliques faster than the long-conjectured barrier for every large enough k, and faster even if matrix multiplication were optimal, with the paper crediting the decisive algebraic decomposition almost purely to the model.

Model
ChatGPT-6 (OpenAI), public web interface, no harness
Field
Computer science
Date
2026-11-06
Human collaborators
Virginia Vassilevska Williams, Or Zamir

What was found

The k-Clique hypothesis holds that the 1985 Nesetril-Poljak reduction is optimal, so that finding a k-clique needs about nωk/3n^{\omega k/3} time, where ω\omega is the matrix multiplication exponent. It is load-bearing in fine-grained complexity: hardness results for parsing, compressed-data problems and many other tasks are proved by reduction from it. The paper gives an algorithm running in n(ω/3−c)kn^{(\omega/3 - c)k} time for a constant c>0c > 0 that does not depend on ω\omega or kk, so the refutation survives even in the ω=2\omega = 2 limit, and it counts weighted k-cliques rather than only detecting one. The engine is a rank-or-swap decomposition that the authors then rewrote in purely combinatorial form, used as a black box inside a human-built algorithmic framework that only needs square matrix multiplication.

Novelty check

Nothing in this registry covered the k-Clique hypothesis before: arXiv, 2026-11-09, abs:"k-Clique" AND (abs:conjecture OR abs:hypothesis) AND abs:"matrix multiplication" returned 11 records, of which this paper is the only refutation and the next nearest is this registry's existing 3SUM and APSP entry (2610.06783). The same search names three concurrent AI-assisted refutations of the related k-HyperClique hypothesis (2611.05082, 2611.03880, 2611.06813), none of which this registry carries yet and none of which is this result. The paper traces its decomposition to OpenAI's October 2026 ETH refutation, which this registry carries as 2026-10-26-eth-refuted-openai.

Caveats and known objections

Days old at the time of writing, with no peer review and no independent confirmation of a claim that invalidates a conditional-hardness premise used widely in the field. Autonomy is collaborative on the authors' own account in Section 6: they supplied the starting ideas for the 5-clique case and the context of recent fine-grained complexity breakthroughs, the model produced the first improvement and the algebraic decomposition, and the authors say the algorithmic framework that uses it is mainly theirs. They also note both of them had the model's memory feature on, so earlier projects could have influenced what it produced, and that the model could not build further on its own obfuscated proofs until a human had simplified them. There is no formalization and no reproducible artifact beyond the paper, so the grade is capped at author verified.

Also recorded at

vibemathedthe-k-clique-hypothesis

Nothing mechanically. It is a parallel listing of the same result, carrying its own verification label rather than an independent check.

Records this paper as the refutation, labels its own verification unreviewed, and says its check on 15 November 2026 read the statement and Theorem 1.1 but not the proofs.

No independent check is recorded on this entry yet.

Reading the primary source closely enough to say whether it supports the claim counts as a check, and you are credited on the entry.

Or on GitHub: submit a check challenge the grade send a correction or send a pull request

History of this entry

  1. CorrectedRecorded the vibemathed record for the k-Clique hypothesis as a registration. No grade moved. source ↗
  2. AddedEntered the registry graded Author verified and Collaborative.

Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.

Graded author verified for verification and collaborative for autonomy. What these mean.

Cite this entry

Plain text
whataifound.org. (2026). Refutation of the k-Clique hypothesis, independent of the matrix multiplication exponent. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-11-06-k-clique-hypothesis-refuted
BibTeX
@misc{whataifound-independent-2026-refuted,
  title        = {Refutation of the k-Clique hypothesis, independent of the matrix multiplication exponent},
  author       = {{whataifound.org}},
  year         = {2026},
  howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
  note         = {Result by Independent (MIT and Tel Aviv University). Verification: Author verified. Autonomy: Collaborative.},
  url          = {https://whataifound.org/finding/2026-11-06-k-clique-hypothesis-refuted}
}

Related findings

← All computer science findings in the registry