Fast nondeterministic matrix multiplication via derandomization of Freivalds' algorithm

DOI10.1007/978-3-662-44602-7_11MaRDI QIDQ3190156zbMATH OpenOpenAlexFDO

Authors Jiří Wiedermann

Publication date 15 September 2014

Published in Advanced Information Systems Engineering (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01402036/file/978-3-662-44602-7_11_Chapter.pdf

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Deterministic verification of integer matrix multiplication in quadratic time
• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• On practical algorithms for accelerated matrix multiplication
• Fast rectangular matrix multiplication and applications
• Compressed matrix multiplication

Cited in

(8)

• 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
• Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification
• Deterministic verification of integer matrix multiplication in quadratic time
• Bounds for semi-disjoint bilinear forms in a unit-cost computational model
• Fast algorithm for the multiplication of a row vector by a randomly selected matrixA
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• Deterministic APSP, Orthogonal Vectors, and More

This page was built for publication: Fast nondeterministic matrix multiplication via derandomization of Freivalds' algorithm

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