An improved combinatorial algorithm for Boolean matrix multiplication

Huacheng Yu

doi:10.1016/j.ic.2018.02.006

An improved combinatorial algorithm for Boolean matrix multiplication

Huacheng Yu

Research output: Contribution to journal › Article › peer-review

25 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	240-247
Number of pages	8
Journal	Information and Computation
Volume	261
DOIs	https://doi.org/10.1016/j.ic.2018.02.006
State	Published - Aug 2018
Externally published	Yes

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

Access to Document

10.1016/j.ic.2018.02.006

Cite this

@article{9d966b7b099645ca9a004d63adac7e39,

title = "An improved combinatorial algorithm for Boolean matrix multiplication",

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.",

keywords = "Boolean matrix multiplication, Combinatorial algorithm, Recursion",

author = "Huacheng Yu",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier Inc.",

year = "2018",

month = aug,

doi = "10.1016/j.ic.2018.02.006",

language = "English (US)",

volume = "261",

pages = "240--247",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - An improved combinatorial algorithm for Boolean matrix multiplication

AU - Yu, Huacheng

PY - 2018/8

Y1 - 2018/8

N2 - 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.

AB - 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.

KW - Boolean matrix multiplication

KW - Combinatorial algorithm

KW - Recursion

UR - http://www.scopus.com/inward/record.url?scp=85042182235&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85042182235&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2018.02.006

DO - 10.1016/j.ic.2018.02.006

M3 - Article

AN - SCOPUS:85042182235

SN - 0890-5401

VL - 261

SP - 240

EP - 247

JO - Information and Computation

JF - Information and Computation

ER -

An improved combinatorial algorithm for Boolean matrix multiplication

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this