Theory of Computing
-------------------
Title : Regularity Lemmas and Combinatorial Algorithms
Authors : Nikhil Bansal and Ryan Williams
Volume : 8
Number : 4
Pages : 69-94
URL : http://www.theoryofcomputing.org/articles/v008a004
Abstract
--------
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 log beta )/(beta w log n)) time algorithm for
BMM where beta = (log* n)^{delta} for some delta > 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 combinatorial methods for CFG parsing, detecting
triangle-freeness, and transitive closure.
- Using Weak Regularity, we also give an algorithm for answering
queries of the form "is S \subseteq V an independent set?" in a
graph. Improving on prior work, we show how to randomly preprocess
a graph in O(n^{2+epsilon}) time (for all epsilon > 0) so that with
high probability, all subsequent batches of log n independent set
queries can be answered deterministically in
O(n^2 (log log n)^2/((log n)^{5/4})) time. When w >= log n, w queries
can be answered in O(n^2 (log log n)^2/((log n)^{7/6})) time. In
addition to its several applications, this problem is interesting
in that it is not known how to do better than O(n^2) using "algebraic"
methods.