Thanks to Robin Kothari for pointing out the following errors in the published version of the article: In the sentence after Theorem 4.2: the O(n^{3/2}) algorithm for Boolean matrix product verification with operations {OR, AND} is not known to be optimal. The Omega(n^{3/2}) lower bound holds for matrix product verfication over the field GF(2). Para 3 after Theorem 5.1: the expected time is O(n^{3/2} \sqrt(w)).