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+ε) elementary operations for any ε > 0