An improved combinatorial algorithm for boolean matrix multiplication

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations

Abstract

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in Ô(n3/ log4 n) time, where the Ô notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan [4] that runs in Ô (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)
Title of host publicationAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
EditorsMagnus M. Halldorsson, Naoki Kobayashi, Bettina Speckmann, Kazuo Iwama
PublisherSpringer Verlag
Pages1094-1105
Number of pages12
ISBN (Print)9783662476710
DOIs
StatePublished - 2015
Externally publishedYes
Event42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan
Duration: Jul 6 2015Jul 10 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9134
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Country/TerritoryJapan
CityKyoto
Period7/6/157/10/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

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

Cite this