k-Clique hypothesis

A k-clique is a set of k vertices with an edge between every pair. For fixed k divisible by three, the standard method splits the candidate clique into three groups and uses matrix multiplication. The hypothesis says that the exponent of this running time cannot be improved by a fixed positive amount in the word-RAM model.

Why it matters and what counts as progress

Why it matters: Many fine-grained reductions use clique detection to explain why other graph and string problems might require a certain running time. A faster clique algorithm changes those comparisons.

What counts as progress: Prove a smaller exponent for a specified range of k, with the computational model and matrix-multiplication baseline stated. A saving relative to the true matrix-multiplication exponent addresses the hypothesis even if that exponent improves.

How the problem developed

  1. 1985 · Matrix-multiplication algorithm [1]

    Jaroslav Nešetřil and Svatopluk Poljak Reduced fixed-size clique detection to triangle detection through matrix multiplication.

  2. 2004 · Algorithmic challenge [2]

    Gerhard J. Woeginger Asked for an improvement on the standard exponent for a fixed clique size.

  3. 6 Nov 2026 · Faster clique counting [3]

    Virginia Vassilevska Williams and Or Zamir with ChatGPT-6 Reported a saving in the exponent for all sufficiently large fixed clique sizes.

AI contribution

The k-Clique hypothesis is dead, for good

Virginia Vassilevska Williams, Or Zamir

For all sufficiently large fixed kk, Vassilevska Williams and Zamir report a word-RAM algorithm that counts kk-cliques in an nn-vertex graph in time O(n(ω−δ)k/3)O(n^{(\omega-\delta)k/3}). Here ω\omega is the square matrix-multiplication exponent and δ>0\delta>0 is independent of kk and ω\omega.

AI involvementAI-centered
ImportanceMajor
Technical verificationReported
Human understandingExplained
Paper date:

Sources

  1. Nešetřil and Poljak’s clique algorithm
  2. Woeginger’s challenge for exact algorithms
  3. The k-Clique hypothesis is dead, for good
Publication history