Efficiently Correcting Matrix Products

Gąsieniec, L ORCID: 0000-0003-1809-9814, Levcopoulos, C, Lingas, A, Pagh, R and Tokuyama, T (2016) Efficiently Correcting Matrix Products. Algorithmica, 79 (2). pp. 428-443.

Text 1602.00435.pdf - Author Accepted Manuscript 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:	19 Jan 2023 07:32
DOI:	10.1007/s00453-016-0202-3
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3003005