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.

## Date:

Mon, 04/06/2018 - 09:00 to 09:50

## Location:

Feldman Building, Givat Ram