Bounds on sample space size for matrix product verification

DOI10.1016/0020-0190(93)90183-AzbMath0818.68093OpenAlexW1989579242MaRDI QIDQ1313769

Donald D. Chinn, Rakesh Kumar Sinha

Publication date: 22 March 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90183-a

zbMATH Keywords

probabilistic algorithmsFreivalds' algorithmprobabilistic matrix product verification algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification ⋮ Bounds on sample space size for matrix product verification

Cites Work

• Matrix multiplication via arithmetic progressions
• 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
• Unnamed Item

This page was built for publication: Bounds on sample space size for matrix product verification