Computing R=P.Q ,the product of two mXm Boolean matrices [BMM] is an ingredient
of many combinatorial algorithms.
Many efforts were made to speed it beyond the standard m^3 steps, without using
the algebraic multiplication.
To divide the computation task, encoding of the rows and column indices were
used (1.1) j by (j1,j2) k by (k1,k2)
e.g. using integer p j2=j mod p ,j1=ceiling of j/p.
Clearly, the product of the ranges of the digits= m1.m2 - is approximately m.
L.Lee’s article reduced BMM to parsing substrings of a fixed string u with
respect to a context-free grammar G. But the cubic complexity persisted.
The reduction here is to a family of bi-graphs bunches, each consisting of
directed graphs. The family is obtained from r distinct encodings (1.1) of
the indices - and invoking the Chinese remainder theorem to produce the BMM R=P.Q.
If r is an integer, e=1/r ,m2=m^(e) then the total number of steps is
2r.m^(2+e). E.g. if r=10 it is 20m^(2.1).
This almost optimal BMM [and simple extensions] replaces the recourse to
complicated algebraic matrix multiplications . It renders its improved
complexity to graph property tests which include BMM as a sub-routine: Finding
all edges which belong to triangles in a graph, using it to reduce complexity
of existence of k-cliques, or edges in 4 vertex diamonds and some other
semi-cliques; Finding all pairs shortest walks in a graph and other applications:
Using Valiant’s reduction of context-free parsing to
BMM, the complexity exponent three in standard parsing is reduced to 2+e with small e.