Efficiently Correcting Matrix Products

We study the problem of efficiently correcting an erroneous product of two n × n matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in Ō(n²+kn) time and a deterministic Ō(kn²)-time algorithm for this problem (where the notation Ō suppresses polylogarithmic terms in n and k).