Deterministic near-quadratic matrix multiplication verification
Fix a constant $c > 0$. In the integer setting, $A, B, C$ are $n \times n$ integer matrices with all entries in $[-n^c, n^c]$, written in binary. In the finite-field setting, they are $n \times n$ matrices over $\mathbb{F}_q$, where $q = p^r \le n^c$ with $p$ prime; elements are written as polynomials of degree less than $r$ over $\mathbb{F}_p$, and an irreducible polynomial of degree $r$ over $\mathbb{F}_p$ defining the field is part of the input. Running time is counted in bit operations. Freivalds's randomised algorithm decides whether $AB = C$ in $\widetilde O(n^2)$ time in both settings. For integer matrices, Künnemann gave a deterministic $\widetilde O(n^2)$-time algorithm that distinguishes $AB = C$ from $AB - C$ having between $1$ and $n$ nonzero entries. Bennett, Gajulapalli, Golovnev and Warton showed that all algorithms in a natural class of deterministic linear-algebraic algorithms need $\Omega(n^\omega)$ time, where $\omega$ is the exponent of matrix multiplication.
Problem. In each of the two settings and for every constant $c > 0$, is there a deterministic algorithm that decides, correctly on every input, whether $AB = C$, using $O(n^2 (\log n)^d)$ bit operations for some constant $d$ that may depend on $c$?
Source: Classical: derandomising Freivalds's algorithm (1979); in this form, Bennett, Gajulapalli, Golovnev and Warton (2024), §1.3, with input encodings and bit costs fixed by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- derandomization, matrix multiplication, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@inproceedings{bennett2024,
author = {Bennett, Huck and Gajulapalli, Karthik and Golovnev, Alexander and Warton, Evelyn},
title = {Matrix Multiplication Verification Using Coding Theory},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
editor = {Kumar, Amit and Ron-Zewi, Noga},
series = {Leibniz Int. Proc. Inform.},
volume = {317},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2024},
pages = {42:1--42:13},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.42},
eprint = {2309.16176},
archivePrefix = {arXiv},
}
@inproceedings{freivalds1979,
author = {Freivalds, R{\=u}si{\c{n}}{\v{s}}},
title = {Fast probabilistic algorithms},
booktitle = {Mathematical Foundations of Computer Science 1979},
series = {Lecture Notes in Comput. Sci.},
volume = {74},
publisher = {Springer},
year = {1979},
pages = {57--69},
doi = {10.1007/3-540-09526-8_5},
}
@inproceedings{kunnemann2018,
author = {K{\"u}nnemann, Marvin},
title = {On Nondeterministic Derandomization of {F}reivalds' Algorithm: Consequences, Avenues and Algorithmic Progress},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
series = {Leibniz Int. Proc. Inform.},
volume = {112},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2018},
pages = {56:1--56:16},
doi = {10.4230/LIPIcs.ESA.2018.56},
eprint = {1806.09189},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ac13,
author = {Townsend, Alex},
title = {{AC-13}: Deterministic near-quadratic matrix multiplication verification},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-13/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00187, "Deterministic near-quadratic matrix multiplication verification", clopen.solutions.