Efficiently Correcting Matrix Products
Gasieniec, Leszek ; Levcopoulos, Christos LU
and Lingas, Andrzej
LU
(2014)
25th International Symposium on Algorithms and Computation (ISAAC), 2014
8889.
p.53-64
- Abstract
- We study the problem of efficiently correcting an erroneous product of two n x n matrices over a ring. We provide a randomized algorithm for correcting a matrix product with k erroneous entries running in (O) over tilde(root kn(2)) time and a deterministic (O) over tilde (kn(2))-time algorithm for this problem (where the notation (O) over tilde suppresses polylogarithmic terms in n and k).
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/7422611
- author
- Gasieniec, Leszek
; Levcopoulos, Christos
LU
and Lingas, Andrzej
LU
- organization
- publishing date
- 2014
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Matrix multiplication, Matrix product verification, Correction, algorithms, Randomized algorithms
- host publication
- Algorithms and Computation, ISAAC 2014
- volume
- 8889
- pages
- 53 - 64
- publisher
- Springer
- conference name
- 25th International Symposium on Algorithms and Computation (ISAAC), 2014
- conference location
- Jeonju, Korea, Republic of
- conference dates
- 2014-12-15 - 2014-12-17
- external identifiers
-
- wos:000354865900005
- scopus:84921487194
- ISSN
- 0302-9743
- 1611-3349
- DOI
- 10.1007/978-3-319-13075-0_5
- language
- English
- LU publication?
- yes
- id
- c8bc6915-7898-4773-a7e7-eac9e8a6d793 (old id 7422611)
- date added to LUP
- 2016-04-01 10:32:44
- date last changed
- 2024-01-06 19:28:55
@inproceedings{c8bc6915-7898-4773-a7e7-eac9e8a6d793,
abstract = {{We study the problem of efficiently correcting an erroneous product of two n x n matrices over a ring. We provide a randomized algorithm for correcting a matrix product with k erroneous entries running in (O) over tilde(root kn(2)) time and a deterministic (O) over tilde (kn(2))-time algorithm for this problem (where the notation (O) over tilde suppresses polylogarithmic terms in n and k).}},
author = {{Gasieniec, Leszek and Levcopoulos, Christos and Lingas, Andrzej}},
booktitle = {{Algorithms and Computation, ISAAC 2014}},
issn = {{0302-9743}},
keywords = {{Matrix multiplication; Matrix product verification; Correction; algorithms; Randomized algorithms}},
language = {{eng}},
pages = {{53--64}},
publisher = {{Springer}},
title = {{Efficiently Correcting Matrix Products}},
url = {{http://dx.doi.org/10.1007/978-3-319-13075-0_5}},
doi = {{10.1007/978-3-319-13075-0_5}},
volume = {{8889}},
year = {{2014}},
}