All reports by Author Amir Abboud:

__
TR23-180
| 17th November 2023
__

Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka#### New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

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

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