Counting $6$-Cliques in $O(n^{5.97})$ time and $O(\log n)$ space
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.
Authors
- Afrouz Jabal Ameli (ORCID: https://orcid.org/0000-0001-5620-9039)
- Jesper Nederlof (ORCID: https://orcid.org/0000-0003-1848-0076)
- Niklas Mohrin (ORCID: https://orcid.org/0009-0004-8296-0167)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.24750
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint