I missed this a month ago, but found the email annoucement in my mbox, which illustrates the benefit of maintaining a good order in one's mbox.
The lack of a satisfying answer to the question of what is a combinatorial (Boolean Matrix Multiplication) algorithm should not impede the search for such algorithms. This assertion is akin to saying that the lack of a definition of what is a combinatorial construction of a PCP (or an LTC) should not have impede the search for such constructions, which has lead to extremely important results. (See further discussion of this issue in Section 1.1 of the paper.)
As for the result itself, the abstract describes it very well: While previous results have already shaved some logarithmic factors (of the naive ``cubic-time'' combinatorial algorithm), the current paper shaves a factor that is super-polylogarithmic.
Note: Three notion of regularity (my take of an overview by Shachar Lovett, 3-Jan-24).
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].
See ECCC TR23-180.