Regularity Lemmas and
Nikhil Bansal, Ryan Williams · 2012
We present new combinatorial algorithms for Boolean matrix multiplication (BMM) and preprocessing a graph to answer independent set queries. We give the first asymptotic improvements on combinatorial algorithms for dense BMM in many years, improving on the Four Russians O(n 3 =(w log n)) bound for machine models with wordsize w. (For a pointer machine, we can set w = log n.) The algorithms utilize notions from Regularity Lemmas for graphs in a novel way. We give two randomized combinatorial algorithms for BMM. The first algorithm is essentially a reduction from BMM to the Triangle Removal Lemma. The best known bounds for the Triangle Removal Lemma only imply an O (n 3 logb)=(b w log n) time algorithm for BMM where b = (log ? n) d for some d > 0, but improvements on the Triangle Removal Lemma would yield corresponding runtime improvements. The second algorithm applies the Weak Regularity Lemma of Frieze and Kannan along with several information compression ideas, running in O n 3 (log log n) 2 =(log n) 9=4 ) time with probability exponentially close to 1. When w log n, it can be implemented in O n 3 (log log n)=(w log n) 7=6 ) time. Our results immediately imply improved com- binatorial methods for CFG parsing, detecting triangle-freeness, and transitive closure.