A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
From MaRDI portal
Publication:1209332
DOI10.1016/0020-0190(93)90224-WzbMath0770.65029OpenAlexW2051391952MaRDI QIDQ1209332
Rakesh Kumar Sinha, Tracy Kimbrel
Publication date: 16 May 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(93)90224-w
design of algorithmsmatrix productserror probabilitybit complexityFreivalds' probabilistic algorithm
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (8)
Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8 ⋮ Efficiently correcting matrix products ⋮ Efficiently Correcting Matrix Products ⋮ Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs ⋮ Unnamed Item ⋮ Certifying algorithms ⋮ A probabilistic algorithm for verifying polynomial middle product in linear time ⋮ Bounds on sample space size for matrix product verification
Cites Work
This page was built for publication: A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
