WorksComputer Science
Counting -Cliques in time and space
Abstract
We present an algorithm that, given read-only access to the adjacency matrix of an -vertex graph , computes the number of -cliques in using time and space. We achieve this by exploiting a decomposition of an equality indicator function underlying, among others, the refutations of the Exponential Time Hypothesis by OpenAI and Anthropic, and of the -Clique Conjecture by Vassilevska Williams and Zamir [arXiv, 2026]. Via known reductions, this implies an time and polynomial space algorithm for Max Cut on -vertex graphs.
Introduction
A clique is a set of pairwise adjacent vertices. Counting fixed-size cliques is a basic problem in graph algorithms. Trivial enumeration counts all -cliques in time. For decades, the fastest known algorithms were based on fast matrix multiplication. The classic reduction of Nešetřil and Poljak [6] counts -cliques in time when is divisible by three, where is the matrix multiplication exponent; rectangular matrix multiplication gives refined bounds for other values of [4]. Until recently, this was the only known route to a polynomial saving over trivial enumeration.
Recent developments go beyond this standard reduction. Vassilevska Williams and Zamir [9] count -cliques in time for all sufficiently large fixed , for an absolute constant independent of both and . The key step in each of these mentioned recent developments are various algebraic decompositions for the equality indicator function that also underlie the recent refutations of the Exponential Time Hypothesis [3, 7].
Given read-only random access to the adjacency matrix, trivial enumeration uses only space for every fixed . Despite the progress on running time, no -time algorithm using only space was previously known for any fixed and constant . The matrix multiplication algorithms do not directly yield such a result. Their standard implementations that run in time linear in the tensor rank of the matrix multiplication tensor achieve their time bounds by sharing intermediate computations between many linear forms and storing polynomial-size arrays. Evaluating the linear forms separately avoids these arrays, but its cost depends on the total support of the decomposition rather than its rank: for known decompositions, this direct evaluation takes more than time.
6-Clique in Logarithmic Space. Building on the mentioned recent developments, we present a decomposition with small enough total support (i.e. a sparse decomposition) that achieves a polynomial saving in the running time and logarithmic space:
Theorem 1. The number of 6-cliques in an -vertex graph can be computed in time and space, given read-only random access to its adjacency matrix.
By the standard reduction of [6 Section 2.2], Theorem 1 can also be used to count (induced) pattern occurrences of any 6-vertex pattern graph. The time–space complexity of fixed-size clique detection has received attention in earlier work. Woeginger [12 Open Problem 4.3(a)] asked for algorithms with improved time and space complexities. Vassilevska [8] gave a combinatorial algorithm that, for every fixed and , detects a -clique in time using space. The stronger goal of obtaining time and polylogarithmic space for some fixed and was explicitly raised by Williams [11 Open Problems].
Our Approach. Like all of these previous recent developments [1, 2, 3, 5, 7, 9] our key step is a decomposition of an equality indicator function. We use it to check equality on 4 vertices and their copies of the 6-clique . Viewing vertex pairs as strings, the decomposition expresses the equality indicator as a sum of terms indexed by a set of swapped indices. At these indices, is matched to and to ; correction factors (which we later factor using anti-commutative indicators) on the remaining indices make the identity exact. We provide two complementary ways to evaluate each resulting term (see also Figure 1).

(a) (a) Clique decomposition used in the factored evaluation. unprimed edges ; primed edges ; primed edges ; .

(b) (b) Clique decomposition used in the direct evaluation. first parenthesis of (3); second parenthesis of (3); fixed: , , , , ; first sum: , , , ; second sum: .
Figure 1. Two decompositions of the fifteen edge tests. (a) The factors , , from Lemma 5, together with the separate edge . (b) In the direct evaluation (3), the first parenthesis tests whether forms a 4-clique, and whether , , while the second tests , , , , , , . Shaded vertices are fixed for these two inner sums; the first sum ranges over , , , , and the second over .
:::
The factored evaluation exploits a sparse factorization to separate the clique-counting expression into a product of sums: after fixing , one factor checks whether is a 4-clique and whether , while the other splits into two independent sums over pairs of vertices once is fixed as well. This evaluation is efficient when few indices are swapped, because the correction factors admit a sparse factorization.
The direct evaluation leaves the equality term unfactored and regroups the edge tests to separate the sum over . It benefits from having many swapped indices: the resulting equalities between and restrict the assignments for which this sum must be computed.
Choosing the faster evaluation for each term yields savings that outweigh the overhead of the decomposition, giving a polynomial improvement over naive enumeration while using only logarithmic space. As mentioned before, our methods are similar to the recent methods for Hyperclique [1, 2, 5], and most closely related to the one for Clique [9]. In comparison with [9], we choose between sparse factored evaluation and direct evaluation for each term to obtain a logarithmic-space algorithm, whereas [9] combines matrix multiplication with recursive reductions to sparser patterns.
Application to Max Cut. In the Max Cut problem one is given an -vertex undirected graph and asked for a subset that maximizes . The problem can be solved in time and exponential space by a reduction to 3-Clique by Williams [10 Section 3]. Using his reduction with six parts reduces unweighted Max Cut to polynomially many 6-clique counting instances on vertices. We represent these instances implicitly, answering each adjacency query in polynomial time and space. Then Theorem 1 implies:
Corollary 2. Max Cut on -vertex graphs can be solved in time and polynomial space.
This resolves the qualitative form of Woeginger’s question [12 Open Problem 4.7(b)] by giving a polynomial-space algorithm with running time for some constant .2
Notation. Throughout this paper we fix an undirected simple input graph and let and denote its vertex and edge set, respectively. We abbreviate and . Write for the indicator of a statement , that is, if is true, and 0 otherwise. We let omit factors polylogarithmic in .
Decomposing String Equalities
We first collect identities about equality indicators, similar to other recent works [1, 2, 3, 5, 7, 9]. Let denote the alphabet size, which we assume to be constant. For strings , we decompose the equality indicator function as follows:
We denote the product in the term as
Thus, . Intuitively, the set specifies for which indices of the strings we swap and ; the factors in are the correcting terms.
We define the anti-commutative indicator to map characters (for ) to
The anti-commutative indicator allows us to factor into two parts, such that one depends only on and , and the other only on and .
Lemma 3. We have
Proof. We use two facts to rewrite each term in . For characters , we have
and
Equation (1) is immediate. For (2), observe that if , the sum vanishes and the indicators agree. If , only contributes, and it gives exactly the left side.3
Starting from the definition of , we use (1) on each factor and (2) on each factor . This gives
Multiplying out this product gives a sum of terms, each of which corresponds to a choice of and for all . Grouping the factors of each term in the final sum into primed and unprimed variables yields the desired equality.
Fix a set . To efficiently evaluate sums that contain a factor, we bound the support of . For strings , we let .
Lemma 4. We have and . Moreover, given and , the elements of can be enumerated in time and space.
Proof. We count the ways to construct the strings while maintaining that . For , we have and . The equality at these indices yields that only of the characters of and can be freely chosen, which establishes the first bound of the lemma. Among all four strings, if , there are ways to choose the characters . For , we consider two cases:
. When choosing , both indicators in the -th factor of are 0. When choosing , both indicators are 1 and cancel. Thus we must set , in which case the factor is .
. Then the second indicator in the -th factor of is 0, so we must set and , in which case the factor is 1.
Thus, for each , there is a binary decision for the case, and in each case there are at most possible choices of characters. Across all characters of all four strings, we get at most choices, yielding the second bound.
Finally, for the enumeration, given and , we first check whether they agree at the indices in . If they do not, then is empty. Otherwise, for each , we choose freely in . For each with , we choose freely in . At every remaining index the pair is forced. By the cases above, the Cartesian product of these choices gives each element of exactly once. We enumerate this product using one counter per index. Since is constant, each counter has constant size. Initializing the counters takes time, and advancing them and producing the next pair takes time per pair. This gives total time and bits of space.
Fast Clique Counting
Fix . Without loss of generality, assume that for some (if needed, we can insert up to isolated vertices into ). Identify vertices with and pairs of vertices with , where . The number of 6-cliques in is . Our algorithm computes the same count as with
where the sum runs over vertices of $G and we denote
Observe that when in , the predicates and check that there is an edge between all pairs of vertices in . Among the variables in , uses only the unprimed variables whereas uses the primed variables . The checks for the edges incident to and are distributed among and .
We split into a family of similar sums by expanding the indicator. Let . Recall that . Going forward, we set , , , and . For a fixed , define
We have . It thus remains to show how we can compute efficiently. In the remainder of this section, we consider two ways to do so. The first exploits a factorization of whereas the second evaluates directly. Both use space, but have varying running time dependent on . Figure 1 visualizes the two computations.
Lemma 5 (Factored Evaluation). can be evaluated in time.
Proof. By using Lemma 3, reordering the sums, and factoring the innermost sum, we obtain
To compute , we can enumerate all possibly-non-zero summands in time. To see this, note that and are forced for , and for , we have either that and or and . We can enumerate all strings and with these properties in time per string, and the value of each summand can be computed in time.
To compute , we expand and simplify the factors based on single characters. We then factor the sum into two parts that depend only on and respectively.^3
To evaluate , we sum over and compute each summand by computing the two inner sums independently. Similar to the argument for computing , both inner sums have at most possibly-non-zero terms and they can be enumerated efficiently: For the first, all non-zero summands satisfy , and for the second all non-zero summands satisfy . The value of each summand can be computed in time.
There are admissible choices of . Hence, the total time to compute is
where we used and that the hides factors.^4
Lemma 6 (Direct Evaluation). can be evaluated in time.
Proof. For fixed , all edge tests involving depend only on these fixed vertices and . We can therefore write as
We evaluate (3) by exhaustively iterating over , , , , and . We then use Lemma 4 to enumerate the values of , , , and for which the factor is non-zero and compute the first inner sum. If this sum is non-zero, we compute the second inner sum over by exhaustive iteration.
For each fixed , the pairs range over . By Lemma 4, and since each enumerated term takes time to evaluate, the total time to compute all first inner sums is
where we used . The first inner sum can be non-zero only if is non-empty. Thus, by Lemma 4, the total time to compute all second inner sums is . Adding the two costs and using , the time this evaluation takes is .
We are now ready to prove our main theorem:
Proof of Theorem 1. To evaluate , we iterate over all sets and compute using whichever of the two methods from Lemmas 5 and 6 is faster. Both first terms are at most . By the binomial theorem, . Therefore the total time is
Using the inequality of and the binomial theorem, we obtain
where we use that
Since , we have and . Substituting into (4) gives
where leaves enough slack to absorb the polylogarithmic factors.
To see that this algorithm uses only space, note that there is only a constant number of sums and that each iterates over values. At any point, only a constant number of variables and intermediate results is stored. When enumerating non-zero terms of a sum, we use counters of size . All intermediate results are of absolute value , thus taking bits.
Open Questions
Our result implies that -Clique can be solved in time and space for fixed . Can -Clique be solved in time and space for some and ? Another open question in the light of the recent work [1, 2, 5] is whether -hyperclique in 3-uniform hypergraphs can be solved in time for some and and space.
AI Methodology
The main construction of this paper was found by OpenAI’s GPT-6 Astra, after we asked it whether sparse factorizations of the -clique tensor can be extracted from [9] in order to derive an time and space algorithm for -Clique for some and . Afterwards ChatGPT was also used for the write-up. The authors reorganized and rewrote the proof.
References
- [1]Josh Alman et al. Finding hypercliques faster than brute force. 2026. arXiv: 2611.05082 [cs.DS]. URL: https://arxiv.org/abs/2611.05082.
- [2]Timothy M. Chan et al. The 3-Uniform Hyperclique Hypothesis is false. 2026. arXiv: 2611.06813 [cs.DS]. URL: https://arxiv.org/abs/2611.06813.
- [3]Claude (Anthropic). A 2^{o(n)} time algorithm for 3-SAT. Preprint. 2026. URL: https://github.com/anthropics/formal-math/tree/main/eth.
- [4]Friedrich Eisenbrand and Fabrizio Grandoni. “On the complexity of fixed parameter clique and dominating set.” In: Theoretical Computer Science 326.1–3 (2004), pp. 57–67. DOI: 10.1016/j.tcs.2004.05.009.DOI
- [5]Nick Fischer. The Hyperclique Hypothesis is false. 2026. arXiv: 2611.03880 [cs.DS]. URL: https://arxiv.org/abs/2611.03880.
- [6]Jaroslav Nešetřil and Svatopluk Poljak. “On the complexity of the subgraph problem.” In: Commentationes Mathematicae Universitatis Carolinae 26.2 (1985), pp. 415–419. URL: https://dml.cz/dmlcz/106381.
- [7]OpenAI. The Exponential Time Hypothesis is false. Preprint. 2026. URL: https://github.com/openai/math/tree/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026.hub.valency.io/works/W_h8uqubsk
- [8]Virginia Vassilevska. “Efficient algorithms for clique problems.” In: Information Processing Letters 109.4 (2009), pp. 254–257. DOI: 10.1016/j.ipl.2008.10.014.
- [9]Virginia Vassilevska Williams and Or Zamir. The k-Clique hypothesis is dead, for good. 2026. arXiv: 2611.09764 [cs.DS]. URL: https://arxiv.org/abs/2611.09764.
- [10]Ryan Williams. “A new algorithm for optimal 2-constraint satisfaction and its implications.” In: Theoretical Computer Science 348.2–3 (2005), pp. 357–365. DOI: 10.1016/j.tcs.2005.09.023.DOI
- [11]Ryan Williams. “Exact Algorithms for Maximum Two-Satisfiability.” In: Encyclopedia of Algorithms. Ed. by Ming-Yang Kao. Springer, 2016, pp. 683–688.
- [12]Gerhard J. Woeginger. “Open problems around exact algorithms.” In: Discret. Appl. Math. 156.3 (2008), pp. 397–405. DOI: 10.1016/J.DAM.2007.03.023. URL: https://doi.org/10.1016/j.dam.2007.03.023.