The Hyperclique Hypothesis is False

AI Disclosure. The results of this paper were obtained in a lengthy chat with ChatGPT Astra 6 (OpenAI) and then refined by Claude Opus 5.5 (Anthropic), in both cases with only minimal human input. Both models also assisted in preparing this write-up. I take full responsibility for the contents of this paper.

Introduction

The goal of fine-grained algorithm design and complexity theory is to pinpoint the best possible running time of every computational problem. On the one hand, this involves designing ever faster algorithms. On the other hand, it involves proving conditional lower bounds, that is, showing that a problem cannot be solved faster than currently known unless some established hardness hypothesis fails. Over the past fifteen years, this approach has developed into a major success story, connecting dozens of polynomial-time problems to a small set of canonical hardness assumptions; see, e.g., [45]. The reasoning behind this approach is not that we treat hypotheses as dogmas, but rather that they mark the current frontier of our algorithmic knowledge: if a problem cannot be solved faster without refuting some hypothesis, then one should first try to refute that hypothesis. In other words, the hypotheses show us where to concentrate our efforts.

We now seem to have entered a new era in which the algorithmic frontier is moving dramatically. Powered by AI systems, several central hardness hypotheses have been refuted within a matter of weeks, in each case by an algebraic algorithm. Among them are the 3SUM Hypothesis [30] and the APSP Hypothesis [46], both refuted by Alman and Vassilevska Williams [6] (see also [33]), as well as the Exponential Time Hypothesis (ETH) [31, 32], refuted independently by OpenAI [40] and Anthropic [18]. Again, this should not be viewed as discouraging, but as exciting progress: the algorithmic frontier has finally moved, and we seem ready to design faster algorithms for many problems.

This paper adds another hypothesis to this list: the Hyperclique Hypothesis, proposed by Lincoln, Vassilevska Williams, and Williams [36]. It states that for all constants $k > h \ge3$ and $\epsilon> 0$, there is no $O(n^{k-\epsilon})$-time algorithm for detecting a $k$-clique in an $h$-uniform hypergraph with $n$ vertices, that is, a set of $k$ vertices any $h$ of which form a hyperedge. The restriction to $h \ge3$ is crucial. For $h = 2$, the problem degenerates to $k$-clique detection in graphs, which can be solved in time $O(n^{\omega k/3})$ (when $k$ is divisible by 3) using fast matrix multiplication [38]; here, $\omega\le9/4$ is the exponent of matrix multiplication [39]. For $h \ge3$, in contrast, no algorithm polynomially faster than exhaustive search was known. The main result of this paper is an algebraic algorithm showing that the Hyperclique Hypothesis is false, for every choice of constants $k > h \ge3$.

Consequences

Over the past years, many conditional lower bounds have been based on the Hyperclique Hypothesis. They concern problems as diverse as Orthogonal Vectors in moderate dimension [1], sparse cycle and hypercycle detection [36, 27], induced 4-cycle detection [22], approximate $n$-pairs shortest paths [21], subgraph isomorphism for patterns of bounded treewidth [14], lowest common ancestors in DAGs [37], first-order model checking and Boolean constraint satisfaction problems [9, 34, 3, 7 FKR25, FKRS26, 24], geometric problems like Klee’s measure problem [Kin22, GK23], diameter computation in geometric intersection graphs [10, 15, 16], discrete $k$-center [17], and $L_\infty$ Hausdorff distance under translations [2], arithmetic problems including 4-SUM [29], and some others [47, 49]. These lower bounds have now lost their basis, so for many of the affected problems we can again hope for faster algorithms than currently known.¹

For several problems, Theorem 1.1 even yields faster algorithms via known reductions. Most notably, for every $h \ge3$, Max-$h$-SAT on $n$ variables can be solved in time $O^*(2^{(1-\delta_h)n})$ for some constant $\delta_h > 0$, and the same holds for Boolean Max-CSPs whose constraints have degree at most $h$ [48, 36]; previously, no such improvement over exhaustive search was known for any $h \ge3$. In fact, the complexity of Max-$h$-SAT has also been suggested as a hardness hypothesis in its own right, including for sparse instances [5]. Moreover, Zero-Weight and Min-Weight $k$-Clique in $h$-uniform hypergraphs can be solved polynomially faster than exhaustive search for every $k > 2h$ [1]; for $h = 2$ this already follows from [6]. Further consequences include faster algorithms for certain weight-$k$ Boolean CSPs, such as Densest $k$-Subhypergraph and Partial Vertex Cover in hypergraphs [34 FKRS25], and polynomially faster algorithms for $(k,h)$-Orthogonal Vectors [24] for $k > h$ with applications to certain first-order optimization problems and Boolean CSPs [7 FKRS25]. Finally, the algorithm behind Theorem 1.1 is general enough to count the induced or non-induced copies of any fixed $k$-vertex pattern in an $h$-uniform hypergraph in time $O(n^{(1-\epsilon_h)k})$ whenever $k > h$.

In addition, Theorem 1.1 refutes the $k$-AP Hypothesis, which was recently proposed by Dudek, Fischer, Gokaj, Jin, Künnemann, Mao, and Redžić [DFG+26]. It states that for every constant $k \ge4$, there is no $O(N^{2-\epsilon})$-time algorithm (for any constant $\epsilon> 0$) for detecting a nontrivial $k$-term arithmetic progression ($k$-AP) in a given set $A \subseteq\{0,\ldots,N\}$. The $k$-AP Hypothesis is known to imply the Hyperclique Hypothesis [DFG+26]: if a $k$-clique in a $(k-1)$-uniform hypergraph can be detected in time $T(n)$, then a $k$-AP can be detected in time $O(T(N^{2/k}))$. Combining this reduction with Theorem 1.1 for $h = k - 1$ yields the following algorithm.

Consequently, the problems that were shown to be hard under the $k$-AP Hypothesis are also open again. These include verifying certain identities in finite algebraic structures [DFG+26] and many of the formerly 3SUM-hard geometric problems [23].

Circumventing the Algebraic Barriers

Before this paper, two barriers suggested that algebraic techniques perhaps cannot speed up hyperclique detection. This subsection explains both barriers in elementary terms, as well as how the new algorithm avoids them.

For starters, consider the matrix multiplication problem. Up to constant factors, computing a matrix product $AB$ is as hard as evaluating the following trilinear polynomial [13]:

For trilinear polynomials like this, the complexity of algebraic algorithms, which may only add, subtract, multiply, and possibly divide numbers [43], is captured by the so-called tensor rank $r$. The reason is that any such algorithm can be rearranged into a rigid form which only computes $r products of three linear forms, (linear combination of the entries of $A$) times (linear combination of the entries of $B$) times (linear combination of the entries of $C$), and adds up these products. Under this characterization, designing fast algebraic algorithms for trilinear polynomials is equivalent to proving upper bounds on their tensor rank. This perspective underlies much of algebraic algorithm design, starting with Strassen’s seminal matrix multiplication algorithm [42]; see, e.g., the survey [12].

Our goal, instead, is to evaluate the 4-linear hyperclique polynomial

Its tensor rank (and even its border rank) is known to be $n^4$ [36], which matches the trivial decomposition into its $n^4$ terms. Thus, the rank-based approach alone, which multiplies four linear combinations of the entries of $A$, $B$, $C$, and $D$, respectively, cannot beat exhaustive search. This is the first barrier.

However, this does not rule out fast algorithms, since for 4-linear polynomials the precise correspondence between algorithms and tensor rank breaks down; see, e.g., [BCK+26, BKW26]. Algorithms now have more freedom; in particular, they can multiply two intermediate results that each depend on two of the inputs. The simplest example is the polynomial $(\sum_i a_i b_i)\cdot(\sum_j c_jd_j)$, which can be evaluated with $2n+1$ multiplications even though its tensor rank is $n^2$. Hence, to beat exhaustive search, an algorithm must form intermediate products that involve just two of the inputs, say, products of entries of $A$ and $B$. A natural way to organize this is to fix an evaluation order, such as $(AB)(CD)$, which determines in which order the inputs are combined and which variables are grouped together. This strategy is formalized by the model of tensor networks studied by Austrin, Kaski, and Kubjas [4], where we fix the evaluation order through a tree and allow rank-based algorithms for combining inputs or intermediate results. This model is strictly more powerful than tensor rank alone. It captures, for example, the fastest known algorithms for counting $k$-cliques in graphs [38], which group the $k$ vertices into three blocks, although the corresponding polynomial has maximal tensor rank (and even maximal border rank) [4]. Nevertheless, Austrin, Kaski, and Kubjas proved that every tensor-network algorithm for $H_3$ takes time $\Omega(n^4)$. This is the second barrier.

To circumvent this second barrier, an algorithm should evaluate different parts of the polynomial in different orders, say, some parts as $(AB)(CD)$ and others as $(BC)(DA)$. The new algorithm does exactly that. It first keeps rearranging $H_3$ as a signed sum of many smaller polynomials. It then evaluates each of these polynomials with whichever of the two pairings $(AB)(CD)$ or $(BC)(DA)$ is cheaper. Intuitively, each pairing is cheap for some of the terms, but neither is cheap for all of them. In other words, every single term is evaluated within the tensor-network model; the gain comes from mixing different evaluation orders for different terms.

Interestingly, this strategy is closely related to Anthropic’s recent refutation of the Exponential Time Hypothesis [18], which also rewrites a count as a signed sum of terms, chooses an efficient evaluation order separately for each term, and recurses. In fact, the two approaches are also connected on a more technical level (see the discussion after Lemma 3.1). OpenAI’s independent ETH refutation [40] also follows a conceptually similar idea.

Further Related Work. The algebraic complexity of hyperclique has also been considered in two very recent works. In [BCK+26], Brand, Curticapean, Kaski, Li, Orzel, Seppelt, and Wang identify obstacles to composing arithmetic circuits, assuming the Hyperclique Hypothesis. In [BKW26], Brand, Kaski, and Wang introduce the two-slice rank, another algebraic measure that captures mixed evaluation orders as above and thus goes beyond tensor networks. They show that it lower-bounds the number of multiplications needed to evaluate a polynomial, and propose proving that the two-slice rank of $H_3$ is $\Omega(n^4)$ as a route towards algebraic hardness of hyperclique. Instead, this paper shows that it is $O(n^{4-\epsilon})$.

Preliminaries

Notation. We write $[n] = \{1,\ldots,n\}$, and $\binom{X}{h}$ for the set of all $h$-element subsets of a set $X$. For a tuple $x = (x_1,\ldots,x_k)$ and a set $S = \{s_1,\ldots,s_h\} \subseteq[k]$, we write $x_S$ for the restriction of $x$ to the entries in $S$. We also write $\hat{x}_i = x_{[k]\setminus\{i\}}$ for the tuple obtained from $x$ by omitting $x_i$. We occasionally write $\operatorname{MM}(a,b,c)$ for the time to multiply an $a \times b$ by a $b \times c$ matrix.

Hyperclique Polynomials. An $h$-uniform hypergraph $G = ([n], E)$ consists of a set $E \subseteq\binom{[n]}{h}$ of hyperedges on the vertex set $[n]$. A $k$-hyperclique in $G$ is a set of $k$ vertices any $h$ of which form a hyperedge. We consider the following algebraic version of this problem: given integer-valued arrays $A_S$ over $[n]^h$, for all $S \in\binom{[k]}{h}$, the goal is to compute the $(k,h)$-hyperclique polynomial

If all arrays $A_S$ are equal to the 0-1-array indicating the hyperedges in $E$, then $H_{k,h}$ is exactly $k!$ times the number of $k$-hypercliques in $G$. In particular, $G$ contains a $k$-hyperclique if and only if $H_{k,h} > 0$. Evaluating $H_{k,h}$ naively takes time $O(n^k)$. We show that $H_{k,h}$ can be evaluated in time $O(n^{(1-\epsilon_h)k})$; this implies Theorem 1.1.

By the following standard reduction [38], it suffices to consider the case $k = h + 1$. Assume that $h + 1$ divides $k$ (otherwise, we first brute-force over $k \bmod(h+1)$ of the variables). We group the $k$ variables into $h + 1$ blocks of equal size and view each block as a single variable ranging over $[n]^{k/(h+1)}$. Each factor $A_{S;x_S}$ depends on only $h$ variables and hence on at most $h$ blocks. We can therefore arrange all factors into $h + 1$ arrays such that the $i$-th array does not depend on the $i$-th block. This is an instance of $H_{h+1,h}$ with $n^{k/(h+1)}$ in place of $n$. Thus, an $O(n^{h+1-\epsilon})$-time algorithm for $H_{h+1,h}$ evaluates $H_{k,h}$ in time $O(n^{(1-\epsilon/(h+1))k})$. From now on, we therefore focus on the case $k = h + 1$, and our goal is to compute $H_h := H_{h+1,h}$.

Model of Computation. We work in the word RAM model with words of $\Theta(\log n)$ bits. All integers arising in the algorithms are polynomially bounded (assuming that the input integers are), so arithmetic operations on them take constant time. Having said that, all algorithms only add, subtract, and multiply numbers, so they can also be implemented in algebraic models of computation, e.g., by arithmetic circuits.

Hyperclique in 3-Uniform Hypergraphs

In this section, we prove Theorem 1.1 for 3-uniform hypergraphs. This case already contains all relevant ideas, and it allows us to present them in their simplest form; the next section extends them to all $h$. Throughout, we stick to basic algebraic language. Our goal is to evaluate the hyperclique polynomial $H_3$, which, for ease of notation, can be stated as follows:

Evaluating $H_3$ naively takes time $O(n^4)$. In this section we show that it can be evaluated in time $O(n^{3.99999})$, thereby proving Theorem 2.1 for the case $h=3$. We have made no attempt to optimize constants.

Generalized Algebraic Formulation

What makes the hyperclique polynomial difficult is that each of its variables $x,y,z,w$ appears in three of the four factors. If every variable appeared in only two factors, as in the polynomial

we would essentially be counting 4-cycles in a graph (taking $A=B=C=D$ to be its adjacency matrix). This polynomial is easy to evaluate: it equals $\operatorname{tr}(ABCD)$, which takes two matrix multiplications and thus time $O(n^\omega)$.

For the algorithm we consider a more general polynomial. It lies between the two cases above: we keep the variables $x,y,z,w$, but $A,B,C,D$ become matrix-valued. Specifically, the entries in $A,B,C,D$ become matrices of the following sizes:

for all $y,z\in[N]$ and $x,w\in[M]$. Then the auxiliary hyperclique polynomial is defined as

Let us call $(N,M,a,b,c)$ the size of this polynomial. This polynomial generalizes the hyperclique polynomial: for $N=M=n$ and $a=b=c=1$, we have $T_3(A,B,C,D)=H_3(A,B,C,D)$. In contrast, for $N=M=1$, the polynomial $T_3(A,B,C,D)=\operatorname{tr}(ABCD)$ has exactly the form of the 4-cycle polynomial above and can be evaluated with two matrix multiplications. The algorithm moves from the first case towards the second by gradually decreasing $N,M$ at the cost of increasing $a,b,c$.

Recursive Algorithm

We describe a simple recursive algorithm to evaluate $T_3$. It repeatedly applies a divide-and-conquer step (Lemma 3.2) and finally evaluates the resulting polynomials using fast matrix multiplication (Lemma 3.3). Throughout, we assume that $N$ and $M$ are powers of some integer constant $q$ to be chosen later. The recursive step is based on the following simple identity:

Proof. The terms $i=j$ are the same on both sides, so fix any pair $i<j$. The last trace expands to $\operatorname{tr}(U_{ij}V_{ij})+\operatorname{tr}(U_{ji}V_{ji})-\operatorname{tr}(U_{ij}V_{ji})-\operatorname{tr}(U_{ji}V_{ij})$. The first two terms are the $(i,j)$ and $(j,i)$ terms of the left-hand side. The last two cancel the $(i,j)$ and $(j,i)$ terms of the first sum on the right.

This identity is not new. For instance, it is exactly the $q \times2$ Cauchy–Binet formula, extended bilinearly to matrices. The $q=2$ swap identity has also appeared in [18 Appendix H], and related identities have shown up for other algorithmic applications, e.g., [41].

• Main terms: After the swap, $B$ and $C$ only depend on $g$, and the summation over $j$ affects only $A$ and $D$. We can therefore move $j$ into the matrix dimension connecting $D$ and $A$. That is, the $g$-th main term $\sum_{j\in[q]} \operatorname{tr}(A^{gj}B^gC^gD^{jg})$ equals $\operatorname{tr}(\bar{A}^g\bar{B}^g\bar{C}^g\bar{D}^g)$ for

• Correction terms: Each of the two factors of the $(i,j)$-th correction term is a difference of two products, which we write as a single product of block matrices. That is, the $(i,j)$-th correction term $\operatorname{tr}((A^{ij}B^i-A^{ji}B^j)(C^jD^{ij}-C^iD^{ji}))$ equals $\operatorname{tr}(\bar{A}^{ij}\bar{B}^{ij}\bar{C}^{ij}\bar{D}^{ij})$ for

Now unfix $x,y,z,w$. The new matrices are chosen in such a way that, e.g., $\bar{A}^g$ and $\bar{A}^{ij}$ only depend on the array $A$, and thus only on the indices $x,y,z$. We may therefore view $\bar{A}^g$ and $\bar{A}^{ij}$ as arrays, where the $xyz$-entry is assigned as described before. All in all, we rewrote $T_3(A,B,C,D)$ as:

This is the claimed identity. The main terms have size $(N/q,M,qa,b,c)$, since the number of rows of $\bar{A}^g$, and equivalently the number of columns of $\bar{D}^g$, has increased by a factor of $q$. Similarly, the correction terms have size $(N/q,M,a,b,2c)$, as the dimension $c$ has doubled. Finally, every entry of the new arrays is an entry of $A$, $B$, $C$, $D$, possibly negated, so the new arrays can be constructed in time linear in the input size (recall that $q$ is a constant).

For the alternative sizes, we apply the same construction to the rotated arrays $C,D,A,B$; by the cyclicity of the trace, this exchanges the roles of $y,z$ and $x,w$, and of $a$ and $b$.

Note that the recursive step only uses the coefficients $1$ and $-1$: every entry of the new arrays is an entry of $A$, $B$, $C$, $D$, possibly negated. In particular, the absolute values of the entries never grow throughout the recursion (e.g., if the input arrays are 0-1-arrays, then all arrays in the recursion have entries in $\{-1,0,1\}$), so we do not have to worry about integers blowing up in this reduction.

Proof. We give two separate algorithms to evaluate $T_3$, which correspond precisely to the two evaluation orders $(AB)(CD)$ and $(BC)(DA)$ from Section 1.2. Which of them is faster depends on the dimensions $a$, $b$, and $c$, and the claimed time bound follows from always executing the faster one.

• In the first algorithm, we pair $A$ with $B$ and $C$ with $D$ and evaluate

To this end, we compute all the matrices $A_{xyz}B_{xyw}$ and $C_{xzw}D_{yzw}$ for all $x,y,z,w$. Afterwards, we can evaluate $T_3$ in time $O(N^4ab)$. To compute the products $A_{xyz}B_{xyw}$, enumerate all $x,y$; omitting $x,y$ from the subscripts, it remains to compute the products $A_zB_w$ for all $z,w$. We stack the matrices $A_1,\ldots,A_N$ on top of each other, put $B_1,\ldots,B_N$ side by side, and compute the product of the resulting large matrices. From this we can read off the desired products $A_zB_w$ for all pairs $z,w$. The products $C_{xzw}D_{yzw}$ are computed symmetrically. The running time is dominated by the $2N^2$ large matrix products. Each has size $Na\times c\times Nb$ and takes time $\operatorname{MM}(Na,c,Nb)$.

• In the second algorithm, we instead pair $B$ with $C$ and $D$ with $A$ to evaluate

Executing the same strategy amounts to computing $N^2$ matrix products of size $Nc\times b\times Nc$ plus $N^2$ matrix products of size $Nc\times a\times Nc$. The final computation of $T_3$ takes time $O(N^4c^2)$, which is again dominated by the matrix products.

The total time is $O\left(N^2\min\{\operatorname{MM}(Na,c,Nb),\operatorname{MM}(Nc,a,Nc)+\operatorname{MM}(Nc,b,Nc)\}\right)$. It suffices to use Strassen’s algorithm [42], which multiplies two $d\times d$ matrices in time $O(d^{\log_2 7})=O(d^{2.81})$. Hence, splitting into square blocks gives $\operatorname{MM}(n,d,m)=O(nm d^{0.81})$ whenever $d\le n,m$ (as is the case here). Since $a^{0.81}+b^{0.81}\le2(ab)^{0.81}$, the total time is $O\left(N^4\min\{ab c^{0.81},(ab)^{0.81}c^2\}\right)$, which is $O\left(N^4(abc)^{0.98}\right)$ when bounding the minimum by the weighted geometric mean with weights $7/8$ and $1/8$. □

Proof of Theorem 2.1 for $h=3$. Let $q$ be a sufficiently large integer constant to be chosen later. By padding the arrays with zeros if necessary, we may assume that $n=q^{2L}$ for some integer $L$; this increases $n$ by at most a constant factor. Viewing the input arrays as arrays of $1\times1$ matrices, $H_3(A,B,C,D)$ is the auxiliary hyperclique polynomial $T_3(A,B,C,D)$ of size $(n,n,1,1,1)$. We now evaluate this polynomial recursively.

We apply Lemma 3.2 recursively for $2L$ levels, alternating between the two reductions. Each call of size $(N,M,a,b,c)$ has $q$ main children of size $(N/q,M,qa,b,c)$ and $\binom{q}{2}$ correction children of size $(N/q,M,a,b,2c)$, or, for the alternative reduction, $q$ main children of size $(N,M/q,a,qb,c)$ and $\binom{q}{2}$ correction children of size $(N,M/q,a,b,2c)$. By Lemma 3.2, the polynomial at each internal node is the sum of the polynomials at its children, so $H_3(A,B,C,D)$ is the sum of the polynomials at the leaves. Each leaf has size $(\sqrt{n},\sqrt{n},a,b,c)$ with $a,b\le q^L=\sqrt{n}$ and $c\le4^L\le\sqrt{n}$, so we can evaluate it by Lemma 3.3.

We analyze the running time. By Lemma 3.2, each internal node in the recursion tree takes time linear in its input size. Its main children together have the same input size as the node itself, and therefore the total input size can only increase from one recursion level to the next. We can thus charge the running time of the internal nodes to the leaves (each of which takes time at least linear in its input size). Naively, this leads to a negligible overhead of $2L=O(\log n)$, but with a slightly more careful analysis this overhead can be avoided.

It remains to analyze the leaves. Define the potential of a node of size $(N,M,a,b,c)$ as $(abc)^{1-\delta}$. The root has potential $1$, and the children of a node with potential $\Phi$ have total potential

this becomes $\rho q^2\Phi$ for

Hence, the leaves have total potential $(\rho q^2)^{2L}=n^2\rho^{2L}$. By Lemma 3.3, a leaf of potential $\Phi$ takes time $O((\sqrt{n})^4\Phi)=O(n^2\Phi)$, so all leaves together take time $O(n^4\rho^{2L})$. Recalling that $L=\log_q(n)/2$, this becomes $O(n^{4-\epsilon})$ for

This shows the trade-off in choosing $q$: it must be large enough to make $(2/q)^\delta$ small, but $\epsilon$ decays with $\log_2q$. We choose $q=2^{400}$. Then, as $\delta=0.02$, we have $(2/q)^\delta<2^{-7}$ and $\log_2(1+2^{-7})<0.012$, and thus $\epsilon>0.008/400=2\cdot10^{-5}$. The total running time is $O(n^{3.99998}\log n)=O(n^{3.99999})$.

As mentioned before, we have made no attempt to optimize the constants. A simple optimization is to rely on the state-of-the-art bounds for square and rectangular matrix multiplication [39, 44]. Analyzing the recursion more carefully, one can then obtain time $O(n^{3.9583})$, but it is likely that much more dramatic improvements are possible.

Hyperclique in $h$-Uniform Hypergraphs

In this section we prove Theorem 2.1 in full generality. To this end, we generalize the algorithm from the previous section from computing $H_3$ to computing $H_h$ for all $h\geq2$. The proof is by induction on $h$. In the base case, for $h=2$, the problem degenerates to matrix multiplication, so that, using Strassen’s algorithm, $H_2$ can be evaluated in time $O(n^{3-\epsilon_2})$ for $\epsilon_2:=3-\log_2 7>0$.

For the inductive step, let $h\geq3$, and assume that $H_{h-1}$ can be evaluated in time $O(n^{h-\epsilon_{h-1}})$ for some constant $0<\epsilon_{h-1}\leq\epsilon_2$ (decreasing $\epsilon_{h-1}$ only weakens this assumption); the goal is to evaluate $H_h$ in time $O(n^{h+1-\epsilon_h})$ for some constant $\epsilon_h>0$. The rest of this section focuses on this inductive step. As in the previous section, it is based on a recursive algorithm that evaluates a more general polynomial $T_h$. Since this closely follows the previous section, we focus on the technical details and only comment on aspects that are new. Throughout, $h$ is a constant, and the $O$-notation hides all factors depending on $h$. For convenience, we express $H_h$ as

In this view the arrays $A,B,C,D$ play the same role as before; the arrays $E_5,\ldots,E_{h+1}$ need extra care.

To define $T_h$, again let $A,B,C,D$ be matrix-valued arrays, where each matrix has size

as in the previous section. In addition, the arrays $E_5,\ldots,E_{h+1}$ have three-dimensional entries:

Abbreviating $E=(E_5,\ldots,E_{h+1})$, the auxiliary hyperclique polynomial is

We call $(N,M,a,b,c)$ its size, where, as before, $x_2,x_3$ range over $[N]$ and $x_1,x_4$ range over $[M]$; the variables $x_5,\ldots,x_{h+1}$ always range over $[n]$. For $N=M=n$ and $a=b=c=1$, we have $T_h=H_h$. For $h=3$, there are no arrays $E_\ell$, and $T_h=\sum_x\operatorname{tr}(A_{\hat{x}_4}B_{\hat{x}_3}C_{\hat{x}_2}D_{\hat{x}_1})$ is exactly the polynomial $T_3$ from the previous section.

The entries of the arrays $E_\ell$ are three-dimensional for the following reason. Each $E_\ell$ depends on all variables $x_1,\ldots,x_4$ that the recursive step splits. Therefore, it has to follow both the main terms, which move digits of these variables into the dimensions $a$ and $b$, and the correction terms, which double the dimension $c$. Its three indices $\alpha$, $\beta$, and $\gamma$ correspond exactly to these three dimensions.

Recursive Algorithm

We now describe the recursive algorithm to evaluate $T_h$. As before, we assume that $N$ and $M$ are powers of some integer constant $q$ to be chosen later.

Proof. We start with the first reduction. As in the proof of Lemma 3.2, we split $x_2,x_3\in[N]$ into their last base-$q$ digit and the remaining digits. This yields arrays $A^{ij},B^i,C^j,D^{ij}$ as before and, since every $E_\ell$ depends on both $x_2$ and $x_3$, arrays $E_\ell^{ij}$ such that

In the previous section, we applied Lemma 3.1 to the matrices $A^{ij}B^i$ and $C^jD^{ij}$. Here, we also have to take the arrays $E_\ell^{ij}$ into account, and we simply attach them to the second factor. For now, fix $x$, and for convenience omit it from the subscripts (e.g., $A^{ij}=A_{\hat{x}_4}^{ij}$). We again let $U_{ij}=A^{ij}B^i$, and we let $V_{ij}\in\mathbb{Z}^{b\times a}$ be the matrix with entries

Without the arrays $E_{\ell}$, this would be exactly the product $C^{j}D^{ij}$. Since $T_h(A^{ij}, B^{i}, C^{j}, D^{ij}, E^{ij})$ is the sum of $\operatorname{tr}(U_{ij}V_{ij})$ over all $x$, we can apply Lemma 3.1 as before. For $A, B, C, D$, we use the same block matrices as in the proof of Lemma 3.2. In the $g$-th main term, the remaining digit $j$ appears in $A$, $D$, and all $E_{\ell}$, and we move it into the dimension $a$ by setting $\bar{E}^{g}_{\ell}[(j,\alpha),\beta,\gamma]=E^{j}_{\ell}[\alpha,\beta,\gamma]$, where we identify $[q]\times[a]$ with $[qa]$ as for the rows of $\bar{A}^{g}$. In the $(i,j)$-th correction term, we set $\bar{E}^{ij}_{\ell}[\alpha,\beta,(1,\gamma)]=E^{ij}_{\ell}[\alpha,\beta,\gamma]$ and $\bar{E}^{ij}_{\ell}[\alpha,\beta,(2,\gamma)]=E^{ij}_{\ell}[\alpha,\beta,\gamma]$, where we identify $[2]\times[c]$ with $[2c]$ as for the columns of $\bar{C}^{ij}$. Then:

where $\alpha'=(j,\alpha)$ ranges over $[qa]$ and $\gamma'=(t,\gamma)$ ranges over $[2c]$. Now unfix $x$. As in the previous section, each new matrix only depends on the indices of the array it is formed from; for instance, $\bar{A}^{g}$ and $\bar{A}^{ij}$ only depend on $\hat{x}_{4}$, and $\bar{E}^{g}_{\ell}$ and $\bar{E}^{ij}_{\ell}$ only depend on $\hat{x}_{\ell}$. We may therefore view the new matrices as arrays indexed by $x$, and summing the above identities over all $x$ yields exactly $T_h(\bar{A}^{g},\bar{B}^{g},\bar{C}^{g},\bar{D}^{g},\bar{E}^{g})$ and $T_h(\bar{A}^{ij},\bar{B}^{ij},\bar{C}^{ij},\bar{D}^{ij},\bar{E}^{ij})$. Every entry of the new arrays is an entry of the old arrays, possibly negated, so the construction takes linear time.

The second reduction is analogous: we split $x_{1}$ and $x_{4}$ instead, which are shared by $B$, $C$, and all $E_{\ell}$. In the main terms, the remaining digit then appears in $B$, $C$, and all $E_{\ell}$, and we move it into the dimension $b$, that is, into the index $\beta$. The correction terms are handled as before. □

The base case uses the induction hypothesis in the following form.

Proof. Let $m=\min\{n_{1},\ldots,n_{h}\}$. Split each range into blocks of size $m$, padding with zeros if necessary. This splits the instance into $O((n_{1}/m)\cdots(n_{h}/m))$ instances of $H_{h-1}$ in which all variables range over $[m]$. Each can be constructed in linear time and evaluated in time $O(m^{h-\epsilon_{h-1}})$. □

Proof. We give three algorithms and run the fastest one. The main difference to the previous section is that, after fixing some of the variables and indices, the remaining sum is again a hyperclique polynomial (of uniformity $h-1$), which we evaluate using Lemma 4.2 instead of matrix multiplication.

• The first algorithm pairs $A$ with $B$, and then evaluates the remaining sum using Lemma 4.2. In detail, we compute the products $W_x=A_{\hat{x}_4}B_{\hat{x}_3}$ for all $x$. This amounts to $N^2n^{h-3}$ matrix

products of size $Na \times c \times Nb$, one for each choice of the variables $x_1,x_2,x_5,\ldots,x_{h+1}$ shared by $A$ and $B$. Using Strassen’s algorithm, this takes time $O(N^{4}n^{h-3}abc^{1-\epsilon_2}) \leq O(N^{4}n^{h-3}abc^{1-\epsilon_{h-1}})$, as we are assuming $\epsilon_{h-1} \leq\epsilon_2$. Afterwards, we fix $x_3,x_4 \in[N]$, $\alpha\in[a]$, and $\beta\in[b]$. The remaining sum

is an instance of $H_{h-1}$ with the $h$ variables $\gamma$, $x_1$, $x_2$, and $x_5,\ldots,x_{h+1}$, since its $h$ factors omit $\gamma$, $x_2$, $x_1$, and $x_5,\ldots,x_{h+1}$, respectively. By Lemma 4.2, it can be evaluated in time $O(c^{1-\epsilon_{h-1}}N^{2}n^{h-3})$. Summing over all $N^2ab$ choices, the first algorithm takes time $O(N^{4}n^{h-3}abc^{1-\epsilon_{h-1}})$ in total.

• The second algorithm instead pairs $B$ with $C$, so that the index $\alpha$ becomes one of the variables of the remaining hyperclique polynomial. Expand $(A_{\widehat{x}_4}B_{\widehat{x}_3})[\alpha,\beta]=\sum_{\kappa\in[c]} A_{\widehat{x}_4}[\alpha,\kappa]\cdot B_{\widehat{x}_3}[\kappa,\beta]$ in the definition of $T_h$, and fix $x_2,x_3\in[N]$, $\beta\in[b]$, and $\gamma,\kappa\in[c]$. It remains to compute

This remaining sum is an instance of $H_{h-1}$ with the $h$ variables $\alpha$, $x_1$, $x_4$, and $x_5,\ldots,x_{h+1}$, since its $h$ factors omit $x_4$, $\alpha$, $x_1$, and $x_5,\ldots,x_{h+1}$, respectively, viewing $B_{\widehat{x}_3}[\kappa,\beta]\cdot C_{\widehat{x}_2}[\beta,\gamma]$ as one factor. By Lemma 4.2, it can be evaluated in time $O(a^{1-\epsilon_{h-1}}N^{2}n^{h-3})$. Summing over all $N^2bc^2$ choices of $x_2,x_3,\beta,\gamma,\kappa$, the second algorithm takes time $O(N^{4}n^{h-3}bc^2a^{1-\epsilon_{h-1}})$.

• The third algorithm is symmetric to the second one and pairs $D$ with $A$, so that the index $\beta$ becomes one of the variables of the remaining hyperclique polynomial. We use the same expansion of $(A_{\widehat{x}_4}B_{\widehat{x}_3})[\alpha,\beta]$, but now fix $x_1,x_4\in[N]$, $\alpha\in[a]$, and $\gamma,\kappa\in[c]$. It remains to compute

This is an instance of $H_{h-1}$ with the $h$ variables $\beta$, $x_2$, $x_3$, and $x_5,\ldots,x_{h+1}$, since its $h$ factors omit $\beta$, $x_3$, $x_2$, and $x_5,\ldots,x_{h+1}$, respectively, viewing $D_{\widehat{x}_1}[\gamma,\alpha]\cdot A_{\widehat{x}_4}[\alpha,\kappa]$ as one factor. By Lemma 4.2, it can be evaluated in time $O(b^{1-\epsilon_{h-1}}N^{2}n^{h-3})$. Summing over all $N^2ac^2$ choices of $x_1,x_4,\alpha,\gamma,\kappa$, the third algorithm takes time $O(N^{4}n^{h-3}ac^2b^{1-\epsilon_{h-1}})$.

The fastest of the three algorithms takes time $O(N^{4}n^{h-3}\min\{abc^{1-\epsilon_{h-1}},a^{1-\epsilon_{h-1}}bc^2,ab^{1-\epsilon_{h-1}}c^2\})$. Bounding the minimum by a weighted geometric mean with weights $1-\epsilon_{h-1}/4$, $\epsilon_{h-1}/8$, and $\epsilon_{h-1}/8$, we obtain

and hence, the fastest algorithm runs in time $O(N^{4}n^{h-3}(abc)^{1-\delta})$ for $\delta=\epsilon_{h-1}^2/8$.

Proof of Theorem 2.1. The proof is by induction on $h$. Recall that in the base case $h = 2$, evaluating $H_2$ degenerates to computing one matrix product. By, e.g., Strassen’s algorithm, this proves the claim for $\epsilon_2 = 3 - \log_2 7 > 0$.

Next, focus on the inductive step for $h \ge3$, i.e., assume that $H_{h-1}$ can be evaluated in time $O(n^{h-\epsilon_{h-1}})$ by the induction hypothesis; we give an algorithm to evaluate $H_h$. Let $\delta= \epsilon_{h-1}^2/8$ and let $q$ be an integer to be determined later. We pad $n$ to $q^{2L}$ for some integer $L$. Then we view $H_h$ as an auxiliary hyperclique polynomial $T_h$ of size $(n,n,1,1,1)$, and design a recursive algorithm to evaluate $T_h$. Apply Lemma 4.1 recursively for $2L$ levels, alternating between the two reductions. Thereby, in the recursion tree, each internal node of size $(N,M,a,b,c)$ has $q$ main children of size $(N/q,M,qa,b,c)$ and $\binom{q}{2}$ correction children of size $(N/q,M,a,b,2c)$, or alternatively $q$ main children of size $(N,M/q,a,qb,c)$ and $\binom{q}{2}$ correction children of size $(N,M/q,a,b,2c)$. Each leaf has size $(\sqrt{n},\sqrt{n},a,b,c)$ with $a,b,c \le\sqrt{n}$, so we can evaluate it by Lemma 4.3.

Since the main children of each node together have the same input size as the node, the internal nodes worsen the running time by at most a factor $O(\log n)$. To analyze the total time of the leaves, associate the potential $(abc)^{1-\delta}$ to any node of size $(N,M,a,b,c)$. A leaf of potential $\Phi$ takes time $O(n^{h-1}\Phi)$, and by the same calculation as before, all leaves together take time $O(n^{h+1-\epsilon})$ for

For $\epsilon$ to be positive, $q$ must be large enough to make $(2/q)^\delta$ small, but then $\epsilon$ decays with $\log_2 q$. We therefore set $q=2^{\lceil(2/\delta)\log_2(1/\delta)\rceil}$. Since $\delta\le1/8$, we have $(2/q)^\delta= 2^{-\delta(\log_2 q-1)} \le2^\delta\delta^2 \le\delta/4$, and thus $\log_2(1+(2/q)^\delta) \le\delta/2$. Together with $\log_2 q \le(3/\delta)\log_2(1/\delta)$, this gives $\epsilon\ge\delta^2/(6\log_2(1/\delta))$. Hence, $H_h$ can be evaluated in time $O(n^{h+1-\epsilon}\log n)=O(n^{h+1-\epsilon_h})$ for $\epsilon_h=\delta^2/(12\log_2(1/\delta))>0$. As a final remark, note that the recursive step only negates entries, and all numbers in the algorithm remain polynomially bounded for polynomially bounded integer inputs. □

The recursion $\epsilon_h=\Omega(\epsilon_{h-1}^4/\log(1/\epsilon_{h-1}))$ shows that $\epsilon_h$ decays doubly exponentially in $h$. We have made no attempt to optimize this dependence.

Acknowledgments

I would like to thank Marvin Künnemann for pointing me to some relevant references.

[1] Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof. More consequences of falsifying SETH and the orthogonal vectors conjecture. In 50th ACM Symposium on Theory of Computing (STOC 2018), pages 253–266. ACM, 2018. {doi}10.1145/3188745.3188983.

[2] Sebastian Angrick, Kevin Buchin, Geri Gökaj, and Marvin Künnemann. Computing $L_\infty$ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness. In 42nd International Symposium on Computational Geometry (SoCG 2026), volume 367 of LIPIcs, pages 7:1–7:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. {doi}10.4230/LIPIcs.SoCG.2026.7.

[AGI⁺21] Haozhe An, Mohit Gurumukhani, Russell Impagliazzo, Michael Jaber, Marvin Künnemann, and Maria Paula G. Nina. The Fine-Grained Complexity of Multi-Dimensional Ordering