Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
Timothy M. Chan · 2014
We present a new combinatorial algorithm for Boolean matrix multiplication that runs in O(n3(log log n)3/log3 n) time. This improves the previous combinatorial algorithm by Bansal and Williams [FOCS'O9] that runs in O(n3(log log n)2/log9/4n) 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.