Advanced

Efficiently Correcting Matrix Products

Gasieniec, Leszek; Levcopoulos, Christos LU and Lingas, Andrzej LU (2014) 25th International Symposium on Algorithms and Computation (ISAAC), 2014 In 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Matrix multiplication, Matrix product verification, Correction, algorithms, Randomized algorithms
in
Algorithms and Computation, ISAAC 2014
volume
8889
pages
53 - 64
publisher
Springer
conference name
25th International Symposium on Algorithms and Computation (ISAAC), 2014
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
2015-06-26 12:06:50
date last changed
2017-09-03 03:18:51
@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},
  keyword      = {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},
  volume       = {8889},
  year         = {2014},
}