Advanced

Efficiently Correcting Matrix Products

Gasieniec, Leszek; Levcopoulos, Christos LU ; Lingas, Andrzej LU ; Pagh, Rasmus and Tokuyama, Takeshi (2016) In Algorithmica
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:
author
organization
publishing date
type
Contribution to journal
publication status
epub
subject
in
Algorithmica
pages
16 pages
publisher
Springer
external identifiers
  • Scopus:84983032223
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
2016-12-05 15:21:22
@misc{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},
  month        = {08},
  pages        = {16},
  publisher    = {ARRAY(0x8a342f0)},
  series       = {Algorithmica},
  title        = {Efficiently Correcting Matrix Products},
  url          = {http://dx.doi.org/10.1007/s00453-016-0202-3},
  year         = {2016},
}