Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > REGULARITY DECOMPOSITION:
Reports tagged with Regularity Decomposition:
TR23-180 | 17th November 2023
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

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




ISSN 1433-8092 | Imprint