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

Algorithms

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › 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).

Originalsprog	Engelsk
Tidsskrift	Algorithmica
Sider (fra-til)	1-16
ISSN	0178-4617
DOI	https://doi.org/10.1007/s00453-016-0202-3
Status	Udgivet - 22 aug. 2016

Emneord

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

Adgang til dokumentet

10.1007/s00453-016-0202-3

210583dcf7d6eb50d1c9aa65099011e66b17Accepteret manuskript, 330 KBLicens: CC BY
10.1007_s00453_016_0202_3Forlagets udgivne version, 2,81 MBLicens: CC BY

Citationsformater

@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",

}

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

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater