Skip to content
Preprint

Counting $6$-Cliques in $O(n^{5.97})$ time and $O(\log n)$ space

Nov 2026 · 0 citations · 11 references
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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.