An improved combinatorial algorithm for Boolean matrix multiplication

摘要

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in (O) over cap (n(3)/log(4)n) time, where the ^ Onotation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in (O) over cap (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). (C) 2018 Elsevier Inc. All rights reserved.