Deterministic verification of integer matrix multiplication in quadratic time

DOI10.1007/978-3-319-04298-5_33MaRDI QIDQ2938115zbMATH OpenOpenAlexFDO

Authors Ivan Korec, Jiří Wiedermann

Publication date 13 January 2015

Published in SOFSEM 2014: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-04298-5_33

Mathematics Subject Classification ID

Matrices of integers (15B36) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40)

Recommendations

• Fast nondeterministic matrix multiplication via derandomization of Freivalds' algorithm
• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• Essentially optimal interactive certificates in linear algebra
• Quadratic-time certificates in linear algebra
• Bounds on sample space size for matrix product verification

Cited in

(11)

• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• Bounds on sample space size for matrix product verification
• The matrix reproved (verification pearl)
• A verified implementation of the Berlekamp-Zassenhaus factorization algorithm
• Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification
• Efficiently correcting matrix products
• Efficiently correcting matrix products
• Bounds for semi-disjoint bilinear forms in a unit-cost computational model
• Fast nondeterministic matrix multiplication via derandomization of Freivalds' algorithm
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• Correcting matrix products over the ring of integers

This page was built for publication: Deterministic verification of integer matrix multiplication in quadratic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938115)