THE SPEED LIMIT FOR FINDING CLIQUES FALLS AFTER 40 YEARS
Picture a social network with n people. Is there a group of k of them who all know one another? Computer scientists call such a group a k-clique, and finding one is a classic problem with countless applications. The naive approach checks every possible group of k people, roughly n^k of them — hopeless for large networks.
A 1985 trick and a long challenge
More than 40 years ago, Jaroslav Nešetřil and Svatopluk Poljak found a shortcut. They turned the search for a k-clique into the search for a triangle (three points all linked to one another) in a bigger network — a “graph”, in the field’s terms —, which in turn can be done by multiplying matrices, big tables of numbers. The cost depends on ω, the exponent of matrix multiplication: multiplying two tables of n by n numbers takes about n^ω steps. Their method takes about n^(ωk/3) steps. Nobody knows ω exactly. It is at least 2, and at most 9/4 (2.25), according to a recent preprint the article cites.
The exponent of that 1985 method was never beaten. In 2004, Gerhard Woeginger challenged researchers to do better for some fixed k; more than two decades passed. Meanwhile the k-Clique Hypothesis — that n^(ωk/3) is essentially the best possible — became a foundation of “fine-grained complexity”, the field that tries to pin down the exact cost of computational problems. Researchers used it to argue that many other problems, from parsing grammars to analysing compressed data, could not be solved faster either.
A moving target
Refuting this hypothesis had a special difficulty. Its predicted cost depends on ω, which is unknown. An algorithm that beats today’s best value of ω could stop beating the hypothesis if someone later found faster matrix multiplication.
Virginia Vassilevska Williams, of MIT, and Or Zamir, of Tel Aviv University, sidestep the problem. They prove that for every large enough k, a k-clique can be found — and even counted — in about n^((ω/3 − c)k) steps, where c is a positive constant that depends neither on k nor on ω. The saving is measured against the true value of ω, whatever it turns out to be. It survives even if ω = 2, the best conceivable case.
Folding a wedge
In short: the authors split one big calculation into a few simpler cases plus a cheap leftover, and together these cost a little less than the whole. The heart of the method concerns patterns of nine vertices (points of the network) linked by edges (the connections between them). The standard approach splits them into three groups of three and multiplies three huge matrices. The authors look at a wedge — two edges sharing a vertex — and insert, between two of the matrices, a table that changes nothing: the identity. They then write that identity as a sum of a few “swaps”, each of which merges the wedge’s two edges into one, plus a leftover of low rank — a table that, despite its size, holds little independent information and is therefore cheap to multiply.
The swaps give simpler patterns with fewer edges, handled by the same method again; a nine-vertex pattern has at most 36 edges, so the recursion ends. The low-rank leftover shrinks the matrices to multiply. Applying the trick to two separate wedges at once is what keeps a gain even when ω = 2. Any k that is a multiple of nine can then be grouped into nine blocks.
Real but tiny
The authors do not give numbers for the gain. They describe the constants as ranging “between minuscule without optimization to tiny with significant optimizations”. The point is not speed in practice: it is that a barrier believed for decades does not exist.
The consequences reach beyond cliques. Exact algorithms for hard optimisation problems such as Max-Cut and Max-2-SAT, which ran in about 2^(ωn/3) steps for n variables, now get a smaller exponent too. So does counting copies of any fixed small graph.
What the AI did
In a dedicated section, the authors describe how they worked with ChatGPT-6, used through its public web interface. Starting from their own ideas for five-person cliques and from a recent OpenAI result refuting another conjecture, the Exponential Time Hypothesis, the model found a first, complicated improvement for 5-cliques. The authors then distilled it, with the AI’s help, into the algebraic decomposition at the core of the proof, which they view as “almost-purely the AI’s contribution”. The algorithmic framework built around it is, they say, mainly theirs.
One remark stands out. Obscure proofs generated by AI are hard for humans to read, the authors note — and they “were impressed that they are also difficult for the AI itself to understand”.
