# An Improved Combinatorial Algorithm for Boolean Matrix Multiplication

arXiv: https://arxiv.org/abs/1505.06811 · HTML: https://mlsanity.com/paper/1505.06811/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2015.

## Built on by (most cited first, 1 of 1)

- [Linear-Time Primitives for Algorithm Development in Graphical Causal Inference](https://mlsanity.com/paper/2506.15758/) (2025)

## Abstract (arXiv)

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in hatO(n3/log4 n) time, where the hatO notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in hatO(n3/log3 n) time. Our algorithm generalizes the divide-and-conquer strategy of Chan's algorithm. Moreover, we propose a general framework for detecting triangles in graphs and computing Boolean matrix multiplication. Roughly speaking, if we can find the "easy parts" of a given instance efficiently, we can solve the whole problem faster than n3.