Finding Hypercliques Faster Than Brute Force

We show that for any fixed k, there exists εₖ > 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(nk-εₖ) 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(nk-εₖ) 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 ε > 0 such that Max-kSAT can be solved in 2(1-ε)n · poly(m,n) time. Second, for every k, there exists ε > 0 such that arithmetic progressions of length k in subsets of \0,1,…,n\ can be detected in n2-ε time. Both corollaries refute other prominent conjectures in the literature.