## New Graph Decompositions
and Combinatorial Boolean Matrix Multiplication Algorithms

by Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, and Raghu Meka

#### Oded's comments

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).

#### The original abstract

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.

Back to
list of Oded's choices.