Efficiently Correcting Matrix Products
We study the problem of efficiently correcting an erroneous product of two n×nn×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 O~(n2+kn)O~(n2+kn) time and a deterministic O~(kn2)O~(kn2)-time algorithm for this problem (where the notation O~O~suppresses polylogarithmic terms in n and k).
