An improved bound on Boolean matrix multiplication for highly clustered data
We consider the problem of computing the product of two n x n Boolean matrices A and B. For two 0 - I strings s = s(1)s(2) .... s(m) and u = u(1)u(2) ... u(m), an extended Hamming distance, eh(s, u), between the strings, is defined by a recursive equation eh(s, u) = eh(s(l+1) ... s(m), u(l+1) ... u(m)) + (s(1) + u(1) mod 2), where l is the maximum number, s.t., s(j) = s, and u(j) = u(1) for j = Fo
