Preprint
Counting $6$-Cliques in $O(n^{5.97})$ time and $O(\log n)$ space
Computer Science
Abstract
We present an algorithm that, given read-only access to the adjacency matrix of an $n$-vertex graph $G$, computes the number of $6$-cliques in $G$ using $O(n^{5.97})$ time and $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 $k$-Clique Conjecture by Vassilevska Williams and Zamir [arXiv, 2026]. Via known reductions, this implies an $O(1.994^n)$ time and polynomial space algorithm for Max Cut on $n$-vertex graphs.