Efficiently Correcting Matrix Products

Leszek Gąsieniec; Christos Levcopoulos; Andrzej Lingas; Rasmus Pagh; Takeshi Tokuyama

doi:10.1007/s00453-016-0202-3

Efficiently Correcting Matrix Products

Leszek Gąsieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, Takeshi Tokuyama

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

We study the problem of efficiently correcting an erroneous product of two 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 Ō(n²+kn) time and a deterministic Ō(kn²)-time algorithm for this problem (where the notation Ō suppresses polylogarithmic terms in n and k).

Original language	English
Journal	Algorithmica
Pages (from-to)	1-16
ISSN	0178-4617
DOIs	https://doi.org/10.1007/s00453-016-0202-3
Publication status	Published - 22 Aug 2016

Keywords

Time complexity
Randomized algorithms
Matrix product correction
Matrix product verification
Matrix multiplication

Access to Document

10.1007/s00453-016-0202-3

210583dcf7d6eb50d1c9aa65099011e66b17Accepted author manuscript, 330 KBLicence: CC BY
10.1007_s00453_016_0202_3Final published version, 2.81 MBLicence: CC BY

Cite this

@article{c284e20ad38949758792fb1ef7aeec1d,

title = "Efficiently Correcting Matrix Products",

abstract = "We study the problem of efficiently correcting an erroneous product of two 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 Ō(n2+kn) time and a deterministic Ō(kn2)-time algorithm for this problem (where the notation Ō suppresses polylogarithmic terms in n and k).",

keywords = "Time complexity, Randomized algorithms, Matrix product correction, Matrix product verification, Matrix multiplication, Time complexity, Randomized algorithms, Matrix product correction, Matrix product verification, Matrix multiplication",

author = "Leszek G{\c a}sieniec and Christos Levcopoulos and Andrzej Lingas and Rasmus Pagh and Takeshi Tokuyama",

year = "2016",

month = aug,

day = "22",

doi = "10.1007/s00453-016-0202-3",

language = "English",

pages = "1--16",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York LLC",

}

TY - JOUR

T1 - Efficiently Correcting Matrix Products

AU - Gąsieniec, Leszek

AU - Levcopoulos, Christos

AU - Lingas, Andrzej

AU - Pagh, Rasmus

AU - Tokuyama, Takeshi

PY - 2016/8/22

Y1 - 2016/8/22

N2 - We study the problem of efficiently correcting an erroneous product of two 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 Ō(n2+kn) time and a deterministic Ō(kn2)-time algorithm for this problem (where the notation Ō suppresses polylogarithmic terms in n and k).

AB - We study the problem of efficiently correcting an erroneous product of two 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 Ō(n2+kn) time and a deterministic Ō(kn2)-time algorithm for this problem (where the notation Ō suppresses polylogarithmic terms in n and k).

KW - Time complexity

KW - Randomized algorithms

KW - Matrix product correction

KW - Matrix product verification

KW - Matrix multiplication

KW - Time complexity

KW - Randomized algorithms

KW - Matrix product correction

KW - Matrix product verification

KW - Matrix multiplication

U2 - 10.1007/s00453-016-0202-3

DO - 10.1007/s00453-016-0202-3

M3 - Journal article

SN - 0178-4617

SP - 1

EP - 16

JO - Algorithmica

JF - Algorithmica

ER -

Efficiently Correcting Matrix Products

Abstract

Keywords

Access to Document

Fingerprint

Cite this