Efficiently Correcting Matrix Products

We study the problem of efficiently correcting an erroneous product of two n x n matrices over a ring. We provide a randomized algorithm for correcting a matrix product with k erroneous entries running in (O) over tilde(root kn(2)) time and a deterministic (O) over tilde (kn(2))-time algorithm for this problem (where the notation (O) over tilde suppresses polylogarithmic terms in n and k)