Combinatorial boolean matrix multiplication runs faster than before

Combinatorial Boolean Matrix Multiplication in $n^3 / 2^{Ω(\sqrt{\log n})}$ Time

Data Structures and Algorithms

Summary

Boolean matrix multiplication is a way to combine two grids of true/false values to find connections, important in many computer problems like detecting triangles in graphs. For decades, the fastest step-by-step (combinatorial) methods only improved speed slightly over the basic cubic time. The authors build on recent advances to create a new deterministic algorithm that cuts down the running time more significantly. They achieve this by better breaking down the problem into manageable parts that are either sparse or highly structured, carefully managing how much information is lost at each step. Their method leads to a faster algorithm that improves on the previous complexity bound.

What this means in practice

  • For graph algorithm developers: Develop faster algorithms for detecting triangles in large networks using improved combinatorial Boolean matrix multiplication.
  • For database system engineers: Optimize complex join operations that rely on Boolean matrix products by incorporating faster deterministic combinatorial methods.

A theory result. No direct application yet.

Authors

Piaoyang Cui, Yiming Liu, David P. Woodruff

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 \emph{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.