Combinatorial Boolean Matrix Multiplication in $n^3 / 2^{Ω(\sqrt{\log n})}$ Time
Piaoyang Cui, Yiming Liu, David P. Woodruff
cs.DS
Nov 4, 2026 · v2
TL;DR
Main theorems on combinatorial BMM and triangle detection are machine-checked in Lean 4 with zero sorries, using a cost-accounting monad for running time.
Abstract
For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abboud, Fischer, Kelley, Lovett, and Meka broke this barrier with a deterministic $O(n^3 / 2^{Ω((\log n)^{1/7})})$-time algorithm, and asked whether $n^3 / 2^{Ω(\sqrt{\log n})}$ time is achievable. We answer this question in the affirmative, giving deterministic combinatorial algorithms for both BMM and triangle detection running in $O(n^3 / 2^{Ω(\sqrt{\log n})})$ time. Following Abboud et al., we decompose $(A,B)$ into pairs of submatrices $(A_k,B_k)$, called pieces, each of which is either sparse or pseudorandom in a sense that forces $A_k\star B_k$ to be nearly all-ones on its vertex sets. Whereas their decomposition produces $2^{O(d^7)}$ pieces at regularity parameter $d$, we obtain $2^{O(d^2)}$ pieces, directly improving the runtime exponent from $(\log n)^{1/7}$ to $\sqrt{\log n}$. Prior work found pseudorandom pieces by repeatedly restricting to denser submatrices, paying worst-case vertex losses at each step that compounded across nested recursion levels, together with an expensive derandomization step. We eliminate the extra powers of $d$ by matching the vertex loss at each step to the size of its density jump so losses telescope across scales, derandomizing witness search via $L_d$-norm estimation so the sampler length stays $2^{O(d)}$, and bounding overlap across the recursion with a fractional density-weighted volume budget rather than raw submatrix volume.
Problem
Combinatorial algorithms for Boolean matrix multiplication and triangle detection long saved only polylogarithmic factors over cubic time. Abboud et al. (STOC 2024) reached n^3/2^{Ω((log n)^{1/7})} and asked whether n^3/2^{Ω(√log n)} is achievable.
Approach
The matrices are decomposed into pieces that are each sparse or pseudorandom (grid-regular), producing 2^{O(d^2)} pieces instead of 2^{O(d^7)}. Vertex losses are matched to density jumps so they telescope across scales, and witness search is derandomized via L_d-norm estimation. Overlap across the recursion is bounded with a fractional density-weighted volume budget. Gemini agents produced the proofs and a Lean 4 formalization; cited sampler and extractor bounds enter as hypotheses, and running time is tracked through a cost monad.
Results
Deterministic combinatorial algorithms for BMM and triangle detection run in O(n^3/2^{Ω(√log n)}) time, answering the open question. Theorems 1.1, 1.3 and Proposition 3.2 are machine-checked in Lean 4 using only the standard axioms.
| Reference | Running time | Main technique |
|---|
| Arlazarov et al. | O(n^3/log^2 n) | Four-Russians |
| Chan | O(n^3 (log log n)^3/log^3 n) | Word-level divide-and-conquer |
| Yu | Ô(n^3/log^4 n) | Compressed tabulation |
| Abboud et al. | O(n^3/2^{Ω((log n)^{1/7})}) | Grid regularity |
| This work | O(n^3/2^{Ω(√log n)}) | Dyadic grid regularity |
Progress on combinatorial BMM and triangle detection