An improved combinatorial algorithm for Boolean matrix multiplication

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in Oˆ(n3/log4⁡n) time, where the Oˆ notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in Oˆ(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.

Original languageEnglish (US)
Pages (from-to)240-247
Number of pages8
JournalInformation and Computation
Volume261
DOIs
StatePublished - Aug 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Boolean matrix multiplication
  • Combinatorial algorithm
  • Recursion

Fingerprint

Dive into the research topics of 'An improved combinatorial algorithm for Boolean matrix multiplication'. Together they form a unique fingerprint.

Cite this