2018
Jun
04

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

9:00am to 9:50am

## Location:

Feldman Building, Givat Ram

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.