TY - GEN

T1 - Speeding up the four Russians algorithm by about one more logarithmic factor

AU - Chan, Timothy M.

N1 - Publisher Copyright:
Copyright © 2015 by the Society for Industrial and Applied Mathmatics.

PY - 2015

Y1 - 2015

N2 - We present a new combinatorial algorithm for Boolean matrix multiplication that runs in 0(re3(log log re)3/log3 n) time. This improves the previous combinatorial algorithm by Bansal and Williams [FOCS'09] that runs in 0(n3(loglog n)2/log9/4 n) time. Whereas Bansal and Williams' algorithm uses regularity lemmas for graphs, the new algorithm is simple and uses entirely elementary techniques: table lookup, word operations, plus a deceptively straightforward divide-and-conquer. Our algorithm is in part inspired by a recent result of Impagliazzo, Lovett, Paturi, and Schneider (2014) on a different geometric problem, offline dominance range reporting; we improve their analysis for that problem as we11.

AB - We present a new combinatorial algorithm for Boolean matrix multiplication that runs in 0(re3(log log re)3/log3 n) time. This improves the previous combinatorial algorithm by Bansal and Williams [FOCS'09] that runs in 0(n3(loglog n)2/log9/4 n) time. Whereas Bansal and Williams' algorithm uses regularity lemmas for graphs, the new algorithm is simple and uses entirely elementary techniques: table lookup, word operations, plus a deceptively straightforward divide-and-conquer. Our algorithm is in part inspired by a recent result of Impagliazzo, Lovett, Paturi, and Schneider (2014) on a different geometric problem, offline dominance range reporting; we improve their analysis for that problem as we11.

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

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

U2 - 10.1137/1.9781611973730.16

DO - 10.1137/1.9781611973730.16

M3 - Conference contribution

AN - SCOPUS:84938269324

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 212

EP - 217

BT - Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

PB - Association for Computing Machinery

T2 - 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Y2 - 4 January 2015 through 6 January 2015

ER -