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

Timothy M. Chan

doi:10.1137/1.9781611973730.16

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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(n³(loglog n)²/log^9/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.

Original language	English (US)
Title of host publication	Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Publisher	Association for Computing Machinery
Pages	212-217
Number of pages	6
Edition	January
ISBN (Electronic)	9781611973747
DOIs	https://doi.org/10.1137/1.9781611973730.16
State	Published - 2015
Externally published	Yes
Event	26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 - San Diego, United States Duration: Jan 4 2015 → Jan 6 2015

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Number	January
Volume	2015-January

Other

Other	26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Country/Territory	United States
City	San Diego
Period	1/4/15 → 1/6/15

ASJC Scopus subject areas

Software
General Mathematics

Online availability

10.1137/1.9781611973730.16

Library availability

Discover UIUC Full Text

Cite this

Chan, T. M. (2015). Speeding up the four Russians algorithm by about one more logarithmic factor. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 (January ed., pp. 212-217). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2015-January, No. January). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973730.16

Speeding up the four Russians algorithm by about one more logarithmic factor. / Chan, Timothy M.
Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January. ed. Association for Computing Machinery, 2015. p. 212-217 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2015-January, No. January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chan, TM 2015, Speeding up the four Russians algorithm by about one more logarithmic factor. in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January edn, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, no. January, vol. 2015-January, Association for Computing Machinery, pp. 212-217, 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, United States, 1/4/15. https://doi.org/10.1137/1.9781611973730.16

@inproceedings{f971aaac8ede414eb7b2a068913a3a5d,

title = "Speeding up the four Russians algorithm by about one more logarithmic factor",

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

author = "Chan, {Timothy M.}",

note = "Publisher Copyright: Copyright {\textcopyright} 2015 by the Society for Industrial and Applied Mathmatics.; 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 ; Conference date: 04-01-2015 Through 06-01-2015",

year = "2015",

doi = "10.1137/1.9781611973730.16",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

number = "January",

pages = "212--217",

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

address = "United States",

edition = "January",

}

TY - GEN

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

AU - Chan, Timothy M.

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 -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this