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

Piaoyang Cui, Yiming Liu, David P. Woodruff

For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abbo…