  We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With
the invention of algebraic fast matrix multiplication over 50 years ago, it
also became known that BMM can be solved in truly subcubic $O(n^\omega)$ time,
where $\omega<3$; much work has gone into bringing $\omega$ closer to $2$.
Since then, a parallel line of work has sought comparably fast combinatorial
algorithms but with limited success. The naive $O(n^3)$-time algorithm was
initially improved by a $\log^2{n}$ factor [Arlazarov et al.; RAS'70], then by
$\log^{2.25}{n}$ [Bansal and Williams; FOCS'09], then by $\log^3{n}$ [Chan;
SODA'15], and finally by $\log^4{n}$ [Yu; ICALP'15].
  We design a combinatorial algorithm for BMM running in time $n^3 /
2^{\Omega(\sqrt[7]{\log n})}$ -- a speed-up over cubic time that is stronger
than any poly-log factor. This comes tantalizingly close to refuting the
conjecture from the 90s that truly subcubic combinatorial algorithms for BMM
are impossible. This popular conjecture is the basis for dozens of fine-grained
hardness results.
  Our main technical contribution is a new regularity decomposition theorem for
Boolean matrices (or equivalently, bipartite graphs) under a notion of
regularity that was recently introduced and analyzed analytically in the
context of communication complexity [Kelley, Lovett, Meka; arXiv'23], and is
related to a similar notion from the recent work on $3$-term arithmetic
progression free sets [Kelley, Meka; FOCS'23].
