Matrix Multiplication Verification Using Coding Theory

Matrix Multiplication Verification Using Coding Theory

Abstract: We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three n × n matrices A, B, and C as input, to decide whether AB = C. A classic randomized algorithm by Freivalds (MFCS, 1979) solves MMV in O(n^2) time, and a longstanding challenge is to (partially) derandomize it while still running in faster than matrix multiplication time (i.e., in o(n^ω) time).

To that end, we give two algorithms for MMV in the case where AB - C is *sparse*. Specifically, when AB - C has at most O(n^δ) non-zero entries for a constant 0 <= δ < 2, we give (1) a deterministic O(n^{ω−ε})-time algorithm for constant ε = ε(δ) > 0, and (2) a randomized O(n^2)-time algorithm using (δ/2) * log_2(n) + O(1) random bits. The former algorithm is faster than the deterministic algorithm of Künnemann (ESA, 2018) when δ >= 1.056, and the latter algorithm uses fewer random bits than the algorithm of Kimbrel and Sinha (IPL, 1993), which runs in the same time and uses log_2(n) + O(1) random bits (in turn fewer than Freivalds's algorithm). Our algorithms are simple and use techniques from coding theory.
Joint work with Karthik Gajulapalli, Alexander Golovnev, and Philip G. Warton.