Finding Hypercliques Faster Than Brute Force

Abstract

We show that for any fixed $k$, there exists ${\epsilon }_k>0$ such that, given a $(k-1)$-uniform hypergraph $H$ on $n$ vertices, one can count the number of $k$-hypercliques in $H$ in $O(n^{k-{\epsilon }_k})$ time. This refutes the hyperclique conjecture of Lincoln, Vassilevska Williams, and Williams (SODA 2018). Our result follows from the uniform construction of a family of arithmetic circuits of size $O(n^{k-{\epsilon }_k})$ for the $k$-hyperclique tensor, a natural higher-order generalization of the matrix multiplication tensor. We obtain two corollaries. First, for every $k$, there exists $\epsilon >0$ such that Max-$k$SAT can be solved in $2^{(1-\epsilon )n}\cdot \mathrm{poly}(m,n)$ time. Second, for every $k$, there exists $\epsilon >0$ such that arithmetic progressions of length $k$ in subsets of $\{0,1,\dots ,n\}$ can be detected in $n^{2-\epsilon }$ time. Both corollaries refute other prominent conjectures in the literature.