Efficiently Correcting Matrix Products



Gąsieniec, L, Levcopoulos, C, Lingas, A, Pagh, R and Tokuyama, T
(2016) Efficiently Correcting Matrix Products. Algorithmica, 79. 428 - 443.

[img] Text
1602.00435.pdf - Accepted Version

Download (338kB)

Abstract

© 2016 The Author(s)We study the problem of efficiently correcting an erroneous product of two (Formula presented.) matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in (Formula presented.) time and a deterministic (Formula presented.)-time algorithm for this problem (where the notation (Formula presented.) suppresses polylogarithmic terms in n and k).

Item Type: Article
Uncontrolled Keywords: Matrix multiplication, Matrix product verification, Matrix product correction, Randomized algorithms, Time complexity
Depositing User: Symplectic Admin
Date Deposited: 22 Aug 2016 15:30
Last Modified: 26 Apr 2022 11:30
DOI: 10.1007/s00453-016-0202-3
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3003005