An Improved Combinatorial Algorithm For Boolean Matrix Multiplication Arxiv
May 26, 2015 - Huacheng Yu
Print
EmailJournal or Book Title: arXiv
Volume/Issue:
Year Published: 2015
We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in O(n3/ log4n) time, where the O notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan [4] that runs in O(n3/ log3n) time. Our algorithm generalizes the divide-and-conquer strategy of Chans 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.
Type of Publication: Journal Paper