Efficiently Correcting Matrix Products
(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
- 1611-3349
- 0302-9743
- 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
- 2025-01-14 17:34:18
@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 = {{1611-3349}}, 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}}, }