HD-Combinatorics: Eli Shamir, "Almost optimal Boolean matrix multiplication[BMM] - By Multi-encoding of rows and columns"

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.


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


Feldman Building, Givat Ram