Efficiently Correcting Matrix Products
Not on the map. Why?
Abstract (arXiv)
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 tildeO(n2+kn) time and a deterministic tildeO(kn2)-time algorithm for this problem (where the notation tildeO suppresses polylogarithmic terms in n and k).
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 1 Feb 2016.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2026: 1.
1 paper.