A Fast Expected Time Algorithm for Boolean Matrix Multiplication and Transitive Closure

A probabilistic algorithm is presented to calculate the Boolean product of two n × n Boolean matrices using an expected number of elementary operations of 0(n2). Asymptotically in n, almost all pairs of matrices may be multiplied using this algorithm in 0(n2+e) elementary operations for any e > 0.