betaFeedback

WorksComputer Science

Counting 66-Cliques in O(n5.97)O(n^{5.97}) time and O(log⁡n)O(\log n) space

Abstract

We present an algorithm that, given read-only access to the adjacency matrix of an nn-vertex graph GG, computes the number of 66-cliques in GG using O(n5.97)O(n^{5.97}) time and O(log⁡n)O(\log n) 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 kk-Clique Conjecture by Vassilevska Williams and Zamir [arXiv, 2026]. Via known reductions, this implies an O(1.994n)O(1.994^n) time and polynomial space algorithm for Max Cut on nn-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 kk-cliques in nkn^k time. For decades, the fastest known algorithms were based on fast matrix multiplication. The classic reduction of Nešetřil and Poljak [6] counts kk-cliques in nωk/3+o(1)n^{\omega k/3+o(1)} time when kk is divisible by three, where ω\omega is the matrix multiplication exponent; rectangular matrix multiplication gives refined bounds for other values of kk [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 kk-cliques in n(ω/3−c)kn^{(\omega/3-c)k} time for all sufficiently large fixed kk, for an absolute constant c>0c > 0 independent of both kk and ω\omega. 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 O(log⁡n)O(\log n) space for every fixed kk. Despite the progress on running time, no O(nk−ε)O(n^{k-\varepsilon})-time algorithm using only (log⁡n)O(1)(\log n)^{O(1)} space was previously known for any fixed k≥3k \ge3 and constant ε>0\varepsilon> 0. 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 nkn^k 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 nn-vertex graph can be computed in O(n5.97)O(n^{5.97}) time and O(log⁡n)O(\log n) 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 k≥3k \ge3 and α>0\alpha> 0, detects a kk-clique in O(nk/(αlog⁡n)k−1)O(n^{k}/(\alpha\log n)^{k-1}) time using O(nα)O(n^{\alpha}) space. The stronger goal of obtaining nk−εn^{k-\varepsilon} time and polylogarithmic space for some fixed k≥3k \ge3 and ε>0\varepsilon> 0 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 {a,b,c,d}\{a,b,c,d\} and their copies {a′,b′,c′,d′}\{a',b',c',d'\} of the 6-clique {a,b,c,d,e,f}\{a,b,c,d,e,f\}. Viewing vertex pairs as strings, the decomposition expresses the equality indicator ⟦ab=a′b′,  cd=c′d′⟧\llbracket ab=a'b',\; cd=c'd'\rrbracket as a sum of terms indexed by a set of swapped indices. At these indices, abab is matched to c′d′c'd' and cdcd to a′b′a'b'; 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).

Clique decomposition used in the factored evaluation. Unprimed edges $U$; primed edges $P_1$ and $P_2$; separate edge $ef$.

(a) (a) Clique decomposition used in the factored evaluation. unprimed edges UU; primed edges P1P_1; primed edges P2P_2; efef.

Clique decomposition used in the direct evaluation. First parenthesis of (3); second parenthesis of (3); fixed: $a$, $b$, $c'$, $d'$, $f$; first sum: $c$, $d$, $a'$, $b'$; second sum: $e$.

(b) (b) Clique decomposition used in the direct evaluation. first parenthesis of (3); second parenthesis of (3); fixed: aa, bb, c′c', d′d', ff; first sum: cc, dd, a′a', b′b'; second sum: ee.

Figure 1. Two decompositions of the fifteen edge tests. (a) The factors UU, P1P_1, P2P_2 from Lemma 5, together with the separate edge efef. (b) In the direct evaluation (3), the first parenthesis tests whether {a,b,c,d}\{a,b,c,d\} forms a 4-clique, and whether a′fa'f, b′f∈E(G)b'f \in E(G), while the second tests aeae, bebe, c′ec'e, d′ed'e, c′fc'f, d′fd'f, efef. Shaded vertices are fixed for these two inner sums; the first sum ranges over cc, dd, a′a', b′b', and the second over ee.

:::

  • The factored evaluation exploits a sparse factorization to separate the clique-counting expression into a product of sums: after fixing ee, one factor checks whether {a,b,c,d}\{a,b,c,d\} is a 4-clique and whether ae,be∈E(G)ae,be \in E(G), while the other splits into two independent sums over pairs of vertices once ff 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 ee. It benefits from having many swapped indices: the resulting equalities between (a,b)(a,b) and (c′,d′)(c',d') 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 nn-vertex undirected graph GG and asked for a subset XX that maximizes ∣{{v,w}∈E(G)∣v∈X,w∉X}∣|\{\{v,w\} \in E(G) \mid v \in X, w \notin X\}|. The problem can be solved in O(2ωn/3)O(2^{\omega n/3}) 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 O(2n/6)O(2^{n/6}) vertices. We represent these instances implicitly, answering each adjacency query in polynomial time and space. Then Theorem 1 implies:

Corollary 2. Max Cut on nn-vertex graphs can be solved in O(1.994n)O(1.994^{n}) 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 O((2−ε)n)O((2-\varepsilon)^n) for some constant ε>0\varepsilon> 0.2

Notation. Throughout this paper we fix an undirected simple input graph GG and let V(G)V(G) and E(G)E(G) denote its vertex and edge set, respectively. We abbreviate n=∣V(G)∣n = |V(G)| and [ℓ]={1,…,ℓ}[\ell] = \{1,\ldots,\ell\}. Write ⟦P⟧\llbracket P\rrbracket for the indicator of a statement PP, that is, ⟦P⟧=1\llbracket P\rrbracket= 1 if PP is true, and 0 otherwise. We let O~(⋅)\widetilde{O}(\cdot) omit factors polylogarithmic in nn.

Decomposing String Equalities

We first collect identities about equality indicators, similar to other recent works [1, 2, 3, 5, 7, 9]. Let q≥2q \ge2 denote the alphabet size, which we assume to be constant. For strings s,s′,w,w′∈[q]ℓs,s',w,w' \in[q]^\ell, we decompose the equality indicator function ⟦s=s′,w=w′⟧\llbracket s=s',w=w'\rrbracket as follows:

⟦s=s′,w=w′⟧=∏i∈[ℓ]⟦si=si′,wi=wi′⟧=∏i∈[ℓ](⟦si=wi′,wi=si′⟧+(⟦si=si′,wi=wi′⟧−⟦si=wi′,wi=si′⟧))=∑S⊆[ℓ]∏i∈S⟦si=wi′,wi=si′⟧∏i∉S(⟦si=si′,wi=wi′⟧−⟦si=wi′,wi=si′⟧).\begin{aligned} \llbracket s=s',w=w'\rrbracket=\prod_{i\in[\ell]}\llbracket s_i=s'_i,w_i=w'_i\rrbracket\\ &=\prod_{i\in[\ell]}\left(\llbracket s_i=w'_i,w_i=s'_i\rrbracket+\left(\llbracket s_i=s'_i,w_i=w'_i\rrbracket-\llbracket s_i=w'_i,w_i=s'_i\rrbracket\right)\right) \\ &=\sum_{S\subseteq[\ell]}\prod_{i\in S}\llbracket s_i=w'_i,w_i=s'_i\rrbracket\prod_{i\notin S}\left(\llbracket s_i=s'_i,w_i=w'_i\rrbracket-\llbracket s_i=w'_i,w_i=s'_i\rrbracket\right). \end{aligned}

We denote the product in the term S⊆[ℓ]S\subseteq[\ell] as

KS(s,w,s′,w′):=∏i∈S⟦si=wi′,wi=si′⟧∏i∉S(⟦si=si′,wi=wi′⟧−⟦si=wi′,wi=si′⟧).K_S(s,w,s',w'):=\prod_{i\in S}\llbracket s_i=w'_i,w_i=s'_i\rrbracket\prod_{i\notin S}\left(\llbracket s_i=s'_i,w_i=w'_i\rrbracket-\llbracket s_i=w'_i,w_i=s'_i\rrbracket\right).

Thus, ⟦s=s′,w=w′⟧=∑S⊆[ℓ]KS(s,w,s′,w′)\llbracket s=s',w=w'\rrbracket=\sum_{S\subseteq[\ell]}K_S(s,w,s',w'). Intuitively, the set SS specifies for which indices of the strings we swap sis_i and wi′w'_i; the factors in [ℓ]∖S[\ell]\setminus S are the correcting terms.

We define the anti-commutative indicator to map characters g,h,x,y∈[q]g,h,x,y\in[q] (for g≠hg\ne h) to

ugh(x,y):={1,(x,y)=(g,h),−1,(x,y)=(h,g),0,otherwise.u_{gh}(x,y):=\begin{cases} 1, & (x,y)=(g,h),\\ -1, & (x,y)=(h,g),\\ 0, & \text{otherwise}. \end{cases}

The anti-commutative indicator allows us to factor KSK_S into two parts, such that one depends only on ss and ww, and the other only on s′s' and w′w'.

Lemma 3. We have

KS(s,w,s′,w′)=∑g,h∈[q]∀i∉S:gi<hi∏i∈S⟦si=gi,wi=hi⟧∏i∉Sugihi(si,wi)∏i∈S⟦si′=hi,wi′=gi⟧∏i∉Sugihi(si′,wi′).K_S(s,w,s',w')=\sum_{\substack{g,h\in[q]\\\forall i\notin S:g_i<h_i}}\prod_{i\in S}\llbracket s_i=g_i,w_i=h_i\rrbracket\prod_{i\notin S}u_{g_ih_i}(s_i,w_i) \prod_{i\in S}\llbracket s'_i=h_i,w'_i=g_i\rrbracket\prod_{i\notin S}u_{g_ih_i}(s'_i,w'_i).

Proof. We use two facts to rewrite each term in KSK_S. For characters x,x′,y,y′∈[q]x,x',y,y'\in[q], we have

⟦x=y′,y=x′⟧=∑g,h∈[q]⟦x=g,y=h⟧⟦x′=h,y′=g⟧.(1)\llbracket x=y',y=x'\rrbracket=\sum_{g,h\in[q]}\llbracket x=g,y=h\rrbracket\llbracket x'=h,y'=g\rrbracket. \tag*{(1)}

and

⟦x=x′,y=y′⟧−⟦x=y′,y=x′⟧=∑g<hugh(x,y)ugh(x′,y′).(2)\llbracket x=x',y=y'\rrbracket-\llbracket x=y',y=x'\rrbracket=\sum_{g<h}u_{gh}(x,y)u_{gh}(x',y'). \tag*{(2)}

Equation (1) is immediate. For (2), observe that if x=yx=y, the sum vanishes and the indicators agree. If x≠yx\ne y, only {g,h}={x,y}\{g,h\}=\{x,y\} contributes, and it gives exactly the left side.3

Starting from the definition of KSK_S, we use (1) on each factor i∈Si\in S and (2) on each factor i∉Si\notin S. This gives

KS(s,w,s′,w′)=∏i∈S∑gi,hi∈[q]⟦si=gi,wi=hi⟧⟦si′=hi,wi′=gi⟧∏i∉S∑gi<hiugihi(si,wi)ugihi(si′,wi′).K_S(s,w,s',w')=\prod_{i\in S}\sum_{g_i,h_i\in[q]}\llbracket s_i=g_i,w_i=h_i\rrbracket\llbracket s'_i=h_i,w'_i=g_i\rrbracket\prod_{i\notin S}\sum_{g_i<h_i}u_{g_ih_i}(s_i,w_i)u_{g_ih_i}(s'_i,w'_i).

Multiplying out this product gives a sum of terms, each of which corresponds to a choice of gig_i and hih_i for all i∈[ℓ]i\in[\ell]. Grouping the factors of each term in the final sum into primed and unprimed variables yields the desired equality.

Fix a set S⊆[ℓ]S \subseteq[\ell]. To efficiently evaluate sums that contain a KSK_S factor, we bound the support of KSK_S. For strings s,w′∈[q]ℓs,w' \in[q]^\ell, we let Ss,w′={(w,s′)∣KS(s,w,s′,w′)≠0}S_{s,w'} = \{(w,s') \mid K_S(s,w,s',w') \ne0\}.

Lemma 4. We have ∣{(s,w′)∣∣Ss,w′∣>0}∣≤q2ℓ−∣S∣\left|\{(s,w') \mid|S_{s,w'}| > 0\}\right| \le q^{2\ell-|S|} and ∑s,w′∣Ss,w′∣≤q2ℓ2ℓ−∣S∣\sum_{s,w'} |S_{s,w'}| \le q^{2\ell}2^{\ell-|S|}. Moreover, given ss and w′w', the elements of Ss,w′S_{s,w'} can be enumerated in O(ℓ(1+∣Ss,w′∣))O(\ell(1+|S_{s,w'}|)) time and O(ℓ)O(\ell) space.

Proof. We count the ways to construct the strings s,w,s′,w′∈[q]ℓs,w,s',w' \in[q]^\ell while maintaining that KS(s,w,s′,w′)≠0K_S(s,w,s',w') \ne0. For i∈Si \in S, we have si=wi′s_i = w'_i and wi=si′w_i = s'_i. The equality si=wi′s_i = w'_i at these indices yields that only 2ℓ−∣S∣2\ell- |S| of the 2ℓ2\ell characters of ss and w′w' can be freely chosen, which establishes the first bound of the lemma. Among all four strings, if i∈Si \in S, there are q2q^2 ways to choose the characters (si,wi,si′,wi′)(s_i,w_i,s'_i,w'_i). For i∉Si \notin S, we consider two cases:

  • si=wi′s_i = w'_i. When choosing wi≠si′w_i \ne s'_i, both indicators in the ii-th factor of KSK_S are 0. When choosing wi=si′=siw_i = s'_i = s_i, both indicators are 1 and cancel. Thus we must set wi=si′≠siw_i = s'_i \ne s_i, in which case the factor is −1-1.

  • si≠wi′s_i \ne w'_i. Then the second indicator in the ii-th factor of KSK_S is 0, so we must set si=si′s_i = s'_i and wi=wi′w_i = w'_i, in which case the factor is 1.

Thus, for each i∉Si \notin S, there is a binary decision for the case, and in each case there are at most q2q^2 possible choices of characters. Across all characters of all four strings, we get at most (q2)∣S∣⋅(2q2)ℓ−∣S∣=q2ℓ⋅2ℓ−∣S∣(q^2)^{|S|} \cdot(2q^2)^{\ell-|S|} = q^{2\ell} \cdot2^{\ell-|S|} choices, yielding the second bound.

Finally, for the enumeration, given ss and w′w', we first check whether they agree at the indices in SS. If they do not, then Ss,w′S_{s,w'} is empty. Otherwise, for each i∈Si \in S, we choose wi=si′w_i = s'_i freely in [q][q]. For each i∉Si \notin S with si=wi′s_i = w'_i, we choose wi=si′w_i = s'_i freely in [q]∖{si}[q] \setminus\{s_i\}. At every remaining index the pair (wi,si′)=(wi′,si)(w_i,s'_i) = (w'_i,s_i) is forced. By the cases above, the Cartesian product of these choices gives each element of Ss,w′S_{s,w'} exactly once. We enumerate this product using one counter per index. Since qq is constant, each counter has constant size. Initializing the counters takes O(ℓ)O(\ell) time, and advancing them and producing the next pair (w,s′)(w,s') takes O(ℓ)O(\ell) time per pair. This gives O(ℓ(1+∣Ss,w′∣))O(\ell(1+|S_{s,w'}|)) total time and O(ℓ)O(\ell) bits of space.

Fast Clique Counting

Fix q=256q = 256. Without loss of generality, assume that n=qtn = q^t for some t≥2t \ge2 (if needed, we can insert up to n⋅qn \cdot q isolated vertices into GG). Identify vertices with [q]t[q]^t and pairs of vertices with [q]ℓ[q]^\ell, where ℓ=2t\ell= 2t. The number of 6-cliques in GG is 16!∑a,b,c,d,e,f∈V(G)1[{a,b,c,d,e,f} is a 6-clique]\frac{1}{6!}\sum_{a,b,c,d,e,f \in V(G)} \mathbb{1}[\{a,b,c,d,e,f\}\text{ is a 6-clique}]. Our algorithm computes the same count as Z/6!Z/6! with

Z:=∑a,b,c,d,e,fa′,b′,c′,d′U(a,b,c,d,e)1[(a,b,c,d)=(a′,b′,c′,d′)]P(a′,b′,c′,d′,e,f)Z := \sum_{\substack{a,b,c,d,e,f\\a',b',c',d'}} U(a,b,c,d,e)\mathbb{1}[(a,b,c,d)=(a',b',c',d')]P(a',b',c',d',e,f)

where the sum runs over vertices of $G and we denote

U(a,b,c,d,e)=1[{a,b,c,d} is a 4-clique in G and ae,be∈E(G)],P(a′,b′,c′,d′,e,f)=P1(a′,c′,e,f)⋅P2(b′,d′,e,f)⋅1[ef∈E(G)],P1(a′,c′,e,f)=1[a′f,c′e,c′f∈E(G)],P2(b′,d′,e,f)=1[b′f,d′e,d′f∈E(G)].\begin{aligned} U(a,b,c,d,e) &= \mathbb{1}[\{a,b,c,d\}\text{ is a 4-clique in }G\text{ and }ae,be \in E(G)],\\ P(a',b',c',d',e,f) &= P_1(a',c',e,f)\cdot P_2(b',d',e,f)\cdot\mathbb{1}[ef \in E(G)],\\ P_1(a',c',e,f) &= \mathbb{1}[a'f,c'e,c'f \in E(G)],\\ P_2(b',d',e,f) &= \mathbb{1}[b'f,d'e,d'f \in E(G)]. \end{aligned}

Observe that when 1[(a,b,c,d)=(a′,b′,c′,d′)]=1\mathbb{1}[(a,b,c,d)=(a',b',c',d')] = 1 in ZZ, the predicates UU and PP check that there is an edge between all pairs of vertices in {a,b,c,d,e,f}\{a,b,c,d,e,f\}. Among the variables in {a,b,c,d,a′,b′,c′,d′}\{a,b,c,d,a',b',c',d'\}, UU uses only the unprimed variables {a,b,c,d}\{a,b,c,d\} whereas PP uses the primed variables {a′,b′,c′,d′}\{a',b',c',d'\}. The checks for the edges incident to ee and ff are distributed among UU and PP.

We split ZZ into a family of similar sums by expanding the indicator. Let s,w,s′,w′∈[q]ℓs,w,s',w' \in[q]^\ell. Recall that ⟦s=s′,w=w′⟧=∑S⊆[ℓ]KS(s,w,s′,w′)\llbracket s=s',w=w'\rrbracket=\sum_{S\subseteq[\ell]}K_S(s,w,s',w'). Going forward, we set s=abs=ab, s′=a′b′s'=a'b', w=cdw=cd, and w′=c′d′w'=c'd'. For a fixed S⊆[ℓ]S\subseteq[\ell], define

ZS:=∑a,b,c,d,e,fa′,b′,c′,d′U(a,b,c,d,e)KS(ab,cd,a′b′,c′d′)P(a′,b′,c′,d′,e,f)Z_S:=\sum_{\substack{a,b,c,d,e,f\\a',b',c',d'}}U(a,b,c,d,e)K_S(ab,cd,a'b',c'd')P(a',b',c',d',e,f)

We have Z=∑S⊆[ℓ]ZSZ=\sum_{S\subseteq[\ell]}Z_S. It thus remains to show how we can compute ZSZ_S efficiently. In the remainder of this section, we consider two ways to do so. The first exploits a factorization of KSK_S whereas the second evaluates KSK_S directly. Both use O(log⁡n)O(\log n) space, but have varying running time dependent on ∣S∣|S|. Figure 1 visualizes the two computations.

Lemma 5 (Factored Evaluation). ZSZ_S can be evaluated in O~(n5+n62∣S∣−t)\widetilde{O}\left(n^5+n^6 2^{|S|-t}\right) time.

Proof. By using Lemma 3, reordering the sums, and factoring the innermost sum, we obtain

ZS=∑e∑g,h∈[q]ℓ∀i∉S:gi<hi(∑a,b,c,dU(a,b,c,d,e)∏i∈S⟦(ab)i=gi,(cd)i=hi⟧∏i∉Sugihi((ab)i,(cd)i))⏟L⋅(∑a′,b′,c′,d′,fP(a′,b′,c′,d′,e,f)∏i∈S⟦(a′b′)i=hi,(c′d′)i=gi⟧∏i∉Sugihi((a′b′)i,(c′d′)i))⏟R.\begin{aligned} Z_S={}&\sum_e\sum_{\substack{g,h\in[q]^\ell\\\forall i\notin S:g_i<h_i}} \underbrace{\left(\sum_{a,b,c,d}U(a,b,c,d,e)\prod_{i\in S}\llbracket(ab)_i=g_i,(cd)_i=h_i\rrbracket\prod_{i\notin S}u_{g_ih_i}((ab)_i,(cd)_i)\right)}_{L}\\ &\qquad\cdot\underbrace{\left(\sum_{a',b',c',d',f}P(a',b',c',d',e,f)\prod_{i\in S}\llbracket(a'b')_i=h_i,(c'd')_i=g_i\rrbracket\prod_{i\notin S}u_{g_ih_i}((a'b')_i,(c'd')_i)\right)}_{R}. \end{aligned}

To compute LL, we can enumerate all possibly-non-zero summands in O~(2ℓ−∣S∣)\widetilde{O}(2^{\ell-|S|}) time. To see this, note that (ab)i=gi(ab)_i=g_i and (cd)i=hi(cd)_i=h_i are forced for i∈Si\in S, and for i∉Si\notin S, we have either that (ab)i=gi(ab)_i=g_i and (cd)i=hi(cd)_i=h_i or (ab)i=hi(ab)_i=h_i and (cd)i=gi(cd)_i=g_i. We can enumerate all strings abab and cdcd with these properties in O(ℓ)O(\ell) time per string, and the value of each summand can be computed in O(ℓ)O(\ell) time.

To compute RR, we expand P(a′,b′,c′,d′,e,f)=⟦ef∈E(G)⟧P1(a′,c′,e,f)P2(b′,d′,e,f)P(a',b',c',d',e,f)=\llbracket ef\in E(G)\rrbracket P_1(a',c',e,f)P_2(b',d',e,f) and simplify the factors based on single characters. We then factor the sum into two parts that depend only on {a′,c′}\{a',c'\} and {b′,d′}\{b',d'\} respectively.^3

R=∑f⟦ef∈E(G)⟧⋅(∑a′,c′P1(a′,c′,e,f)∏i∈S∩[t]⟦ai′=hi,ci′=gi⟧∏i∈[t]∖Sugihi(ai′,ci′))⋅(∑b′,d′P2(b′,d′,e,f)∏i∈[t]t+i∈S⟦bi′=ht+i,di′=gt+i⟧∏i∈[t]t+i∉Sugt+iht+i(bi′,di′)).\begin{aligned} R={}&\sum_f\llbracket ef\in E(G)\rrbracket\cdot\left(\sum_{a',c'}P_1(a',c',e,f)\prod_{i\in S\cap[t]}\llbracket a'_i=h_i,c'_i=g_i\rrbracket\prod_{i\in[t]\setminus S}u_{g_ih_i}(a'_i,c'_i)\right)\\ &\qquad\cdot\left(\sum_{b',d'}P_2(b',d',e,f)\prod_{\substack{i\in[t]\\t+i\in S}}\llbracket b'_i=h_{t+i},d'_i=g_{t+i}\rrbracket\prod_{\substack{i\in[t]\\t+i\notin S}}u_{g_{t+i}h_{t+i}}(b'_i,d'_i)\right). \end{aligned}

To evaluate RR, we sum over ff and compute each summand by computing the two inner sums independently. Similar to the argument for computing LL, both inner sums have at most 2t2^t possibly-non-zero terms and they can be enumerated efficiently: For the first, all non-zero summands satisfy (ai′,ci′)∈{(gi,hi),(hi,gi)}(a'_i,c'_i)\in\{(g_i,h_i),(h_i,g_i)\}, and for the second all non-zero summands satisfy (bi′,di′)∈{(gt+i,ht+i),(ht+i,gt+i)}(b'_i,d'_i)\in\{(g_{t+i},h_{t+i}),(h_{t+i},g_{t+i})\}. The value of each summand can be computed in O(ℓ)O(\ell) time.

There are q2∣S∣(q2)ℓ−∣S∣q^{2|S|}\binom{q}{2}^{\ell-|S|} admissible choices of (g,h)(g,h). Hence, the total time to compute ZSZ_S is

O~(n⋅q2∣S∣(q2)ℓ−∣S∣(2ℓ−∣S∣+n2t))≤O~(n⋅q2ℓ2∣S∣−ℓ(2ℓ−∣S∣+n2t))=O~(n5+n62∣S∣−t)\widetilde{O}\left(n\cdot q^{2|S|}\binom{q}{2}^{\ell-|S|}\left(2^{\ell-|S|}+n2^t\right)\right)\leq\widetilde{O}\left(n\cdot q^{2\ell}2^{|S|-\ell}\left(2^{\ell-|S|}+n2^t\right)\right)=\widetilde{O}\left(n^5+n^6 2^{|S|-t}\right)

where we used q2ℓ=n4q^{2\ell}=n^4 and that the O~\widetilde{O} hides ℓ=O(log⁡n)\ell=O(\log n) factors.^4

Lemma 6 (Direct Evaluation). ZSZ_S can be evaluated in O~(n52ℓ−∣S∣+n6qℓ−∣S∣)\widetilde{O}(n^{5}2^{\ell-|S|}+n^{6}q^{\ell-|S|}) time.

Proof. For fixed a,b,c′,d′,fa,b,c',d',f, all edge tests involving ee depend only on these fixed vertices and ee. We can therefore write ZSZ_S as

ZS=∑a,b,c′,d′,f(∑c,d,a′,b′KS(ab,cd,a′b′,c′d′)⋅1[{a,b,c,d} is a 4-clique in G]1[a′f,b′f∈E(G)])⋅(∑e1[ae,be,c′e,d′e,c′f,d′f,ef∈E(G)]).(3)Z_S=\sum_{a,b,c',d',f}\left(\sum_{c,d,a',b'}K_S(ab,cd,a'b',c'd')\cdot\mathbb{1}[\{a,b,c,d\}\text{ is a 4-clique in }G]\mathbb{1}[a'f,b'f\in E(G)]\right)\cdot\left(\sum_e\mathbb{1}[ae,be,c'e,d'e,c'f,d'f,ef\in E(G)]\right). \tag*{(3)}

We evaluate (3) by exhaustively iterating over aa, bb, c′c', d′d', and ff. We then use Lemma 4 to enumerate the values of a′a', b′b', cc, and dd for which the KSK_S factor is non-zero and compute the first inner sum. If this sum is non-zero, we compute the second inner sum over ee by exhaustive iteration.

For each fixed ff, the pairs (s,w′)=(ab,c′d′)(s,w')=(ab,c'd') range over [q]ℓ×[q]ℓ[q]^\ell\times[q]^\ell. By Lemma 4, and since each enumerated term takes O(ℓ)O(\ell) time to evaluate, the total time to compute all first inner sums is

O(ℓn5+ℓn∑s,w′∣Ss,w′∣)=O(ℓn5+ℓnq2ℓ2ℓ−∣S∣)=O~(n52ℓ−∣S∣),O\left(\ell n^5+\ell n\sum_{s,w'}|S_{s,w'}|\right)=O\left(\ell n^5+\ell nq^{2\ell}2^{\ell-|S|}\right)=\widetilde{O}\left(n^52^{\ell-|S|}\right),

where we used q2ℓ=n4q^{2\ell}=n^4. The first inner sum can be non-zero only if Ss,w′S_{s,w'} is non-empty. Thus, by Lemma 4, the total time to compute all second inner sums is O~(n⋅q2ℓ−∣S∣⋅n)\widetilde{O}(n\cdot q^{2\ell-|S|}\cdot n). Adding the two costs and using q2ℓ=n4q^{2\ell}=n^4, the time this evaluation takes is O~(n52ℓ−∣S∣+n6qℓ−∣S∣)\widetilde{O}(n^52^{\ell-|S|}+n^6q^{\ell-|S|}).

We are now ready to prove our main theorem:

Proof of Theorem 1. To evaluate ZZ, we iterate over all sets SS and compute ZSZ_S using whichever of the two methods from Lemmas 5 and 6 is faster. Both first terms are at most n52ℓ−∣S∣n^52^{\ell-|S|}. By the binomial theorem, ∑S⊆[ℓ]2ℓ−∣S∣=∑j=0ℓ(ℓj)2ℓ−j=3ℓ=9t\sum_{S\subseteq[\ell]}2^{\ell-|S|}=\sum_{j=0}^{\ell}\binom{\ell}{j}2^{\ell-j}=3^\ell=9^t. Therefore the total time is

O~(n59t+n6∑S⊆[ℓ]min⁡{2∣S∣−t,q−∣S∣}).(4)\widetilde{O}\left(n^59^t+n^6\sum_{S\subseteq[\ell]}\min\{2^{|S|-t},q^{-|S|}\}\right). \tag*{(4)}

Using the inequality min⁡{x,y}≤xy\min\{x,y\}\le\sqrt{xy} of x,y∈R≥0x,y\in\mathbb{R}_{\geq0} and the binomial theorem, we obtain

∑S⊆[ℓ]min⁡{2∣S∣−t,q−∣S∣}≤2−t/2∑S⊆[ℓ](2/q)∣S∣/2=2−t/2(1+2/q)2t=2−t/2(1+1/128)2t<2−t/4,\begin{aligned} \sum_{S\subseteq[\ell]}\min\{2^{|S|-t},q^{-|S|}\}\le2^{-t/2}\sum_{S\subseteq[\ell]}(2/q)^{|S|/2} \\ &=2^{-t/2}(1+\sqrt{2/q})^{2t}=2^{-t/2}(1+\sqrt{1/128})^{2t}<2^{-t/4}, \end{aligned}

where we use that

(1+1/128)22<0.838<2−1/4.\frac{(1+\sqrt{1/128})^2}{\sqrt{2}}<0.838<2^{-1/4}.

Since n=256tn=256^t, we have 9t<n9^t<\sqrt{n} and 2−t/4=n−1/322^{-t/4}=n^{-1/32}. Substituting into (4) gives

O~(n11/2+n6−1/32)=O(n5.97),\widetilde{O}(n^{11/2}+n^{6-1/32})=O(n^{5.97}),

where 6−1/32=5.96875<5.976-1/32=5.96875<5.97 leaves enough slack to absorb the polylogarithmic factors.

To see that this algorithm uses only O(log⁡n)O(\log n) space, note that there is only a constant number of sums and that each iterates over nO(1)n^{O(1)} 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 O(ℓ)=O(log⁡n)O(\ell)=O(\log n). All intermediate results are of absolute value nO(1)n^{O(1)}, thus taking O(log⁡n)O(\log n) bits.

Open Questions

Our result implies that kk-Clique can be solved in O(nk−0.03)O(n^{k-0.03}) time and O(log⁡n)O(\log n) space for fixed k≥6k \ge6. Can kk-Clique be solved in O(nk−ε)O(n^{k-\varepsilon}) time and log⁡O(1)(n)\log^{O(1)}(n) space for some ε>0\varepsilon> 0 and k=3,4,5k = 3, 4, 5? Another open question in the light of the recent work [1, 2, 5] is whether kk-hyperclique in 3-uniform hypergraphs can be solved in time O(nk−ε)O(n^{k-\varepsilon}) for some ε>0\varepsilon> 0 and kk and log⁡O(1)(n)\log^{O(1)}(n) 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 kk-clique tensor can be extracted from [9] in order to derive an O(nk−ε)O(n^{k-\varepsilon}) time and log⁡O(1)(n)\log^{O(1)}(n) space algorithm for kk-Clique for some ε∈R>0\varepsilon\in\mathbb{R}_{>0} and k∈Z>0k \in\mathbb{Z}_{>0}. Afterwards ChatGPT was also used for the write-up. The authors reorganized and rewrote the proof.

References

  1. [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. [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. [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. [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. [5]Nick Fischer. The Hyperclique Hypothesis is false. 2026. arXiv: 2611.03880 [cs.DS]. URL: https://arxiv.org/abs/2611.03880.
  6. [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. [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. [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. [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. [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. [11]Ryan Williams. “Exact Algorithms for Maximum Two-Satisfiability.” In: Encyclopedia of Algorithms. Ed. by Ming-Yang Kao. Springer, 2016, pp. 683–688.
  12. [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.

Paper details

vlnc:W_4mbc8ygx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents