Imagine a device that multiplies two matrices very fast, but unreliably: only a small constant fraction of the entries in its output are correct, and even this is guaranteed only when the input matrices are random. On the matrices you actually care about, it may behave arbitrarily badly. Can such a device still be useful?
In this talk, we will see a recent result of Hirahara and Shimizu (STOC 2025) showing that the answer is yes, in the strongest possible sense: any such device can be converted into a fast randomized algorithm that computes matrix multiplication exactly, on all inputs. Over a finite field with $p$ elements, one can always get a $1/p$ fraction of entries right by blind guessing; the result shows that any algorithm doing even slightly better than this trivial baseline can be fully error-corrected, so the threshold is optimal. This is what is called a “worst-case exact to average-case approximate” reduction, and it resolves a question left open by earlier work on the average-case complexity of matrix multiplication.
A central idea in the proof comes from the theory of error-correcting codes. Instead of feeding the matrices $A$ and $B$ to the unreliable device directly, we first encode them: applying a linear code with encoding matrix $Q$, we hand the device the matrices $QA$ and $(QB^{\perp})^{\perp}$. The point is that the product of these encoded matrices equals $QABQ^{\perp}$, which is precisely the answer $AB$ encoded from the left and the right. The device’s noisy output is therefore a corrupted codeword of this two-sided encoding, and if the underlying code is a good list-decodable, such as the Reed-Solomon code, we can decode it column by column and then row by row to recover a short list of candidates containing $AB$, from which the true product is identified by a fast randomized verification. The talk will be self-contained and should be accessible to anyone comfortable with basic linear algebra and probability.
Resources
References: Paper Link