Efficiently Correcting Matrix Products
Gasieniec, Leszek ; Levcopoulos, Christos LU
; Lingas, Andrzej
LU
; Pagh, Rasmus
and Tokuyama, Takeshi
(2017)
In Algorithmica
79(2).
p.428-443
- Abstract
- We study the problem of efficiently correcting an erroneous product of two n×n
n×n 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 O~(n2+kn)
O~(n2+kn) time and a deterministic O~(kn2)
O~(kn2)-time algorithm for this problem (where the notation O~
O~suppresses polylogarithmic terms in n and k).
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/07ff6fdc-af95-4109-b547-76926cf9c896
- author
- Gasieniec, Leszek
; Levcopoulos, Christos
LU
; Lingas, Andrzej
LU
; Pagh, Rasmus
and Tokuyama, Takeshi
- organization
- publishing date
- 2017-10
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Algorithmica
- volume
- 79
- issue
- 2
- pages
- 428 - 443
- publisher
- Springer
- external identifiers
-
- scopus:84983032223
- wos:000406779100007
- ISSN
- 0178-4617
- DOI
- 10.1007/s00453-016-0202-3
- language
- English
- LU publication?
- yes
- id
- 07ff6fdc-af95-4109-b547-76926cf9c896
- date added to LUP
- 2016-08-25 07:57:30
- date last changed
- 2025-10-14 11:51:49
@article{07ff6fdc-af95-4109-b547-76926cf9c896,
abstract = {{We study the problem of efficiently correcting an erroneous product of two n×n<br/>n×n 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 O~(n2+kn)<br/>O~(n2+kn) time and a deterministic O~(kn2)<br/>O~(kn2)-time algorithm for this problem (where the notation O~<br/>O~suppresses polylogarithmic terms in n and k).}},
author = {{Gasieniec, Leszek and Levcopoulos, Christos and Lingas, Andrzej and Pagh, Rasmus and Tokuyama, Takeshi}},
issn = {{0178-4617}},
language = {{eng}},
number = {{2}},
pages = {{428--443}},
publisher = {{Springer}},
series = {{Algorithmica}},
title = {{Efficiently Correcting Matrix Products}},
url = {{https://lup.lub.lu.se/search/files/11372501/10.1007_s00453_016_0202_3.pdf}},
doi = {{10.1007/s00453-016-0202-3}},
volume = {{79}},
year = {{2017}},
}