An Improved Combinatorial Algorithm for Boolean Matrix Multiplication

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in

$$\hat{O}(n^3/\log ^4 n)$$

O

^

(

n

3

/

log

4

n

)

time, where the

$$\hat{O}$$

O

^

notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan [

4

] that runs in

$$\hat{O}(n^3/\log ^3 n)$$

O

^

(

n

3

/

log

3

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

$$n^3$$

n

3

.