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

INF - System Information Sciences

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

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 O~ (n²+ kn) time and a deterministic O~ (kn²) -time algorithm for this problem (where the notation O~ suppresses polylogarithmic terms in n and k).

Original language	English
Pages (from-to)	428-443
Number of pages	16
Journal	Algorithmica
Volume	79
Issue number	2
DOIs	https://doi.org/10.1007/s00453-016-0202-3
Publication status	Published - 2017 Oct 1

Keywords

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

ASJC Scopus subject areas

Computer Science(all)
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-016-0202-3

Cite this

@article{9d54562ef0744a6f8c68871dd050d015,

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 O~ (n2+ kn) time and a deterministic O~ (kn2) -time algorithm for this problem (where the notation O~ suppresses polylogarithmic terms in n and k).",

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

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

note = "Funding Information: We thank anonymous referees for helping us to improve preliminary versions of this paper. Christos Levcopoulos and Andrzej Lingas were supported in part by Swedish Research Council Grant 621-2011-6179. Takeshi Tokuyama was supported by JSPS Grant Scientific Research (B) 15H02665, JSPS Scientific Research for Innovative Area 24106007, and JST ERATO Kawarabayashi Big-Graph Project. Publisher Copyright: {\textcopyright} 2016, The Author(s).",

year = "2017",

month = oct,

day = "1",

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

language = "English",

volume = "79",

pages = "428--443",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Efficiently Correcting Matrix Products

AU - Gąsieniec, Leszek

AU - Levcopoulos, Christos

AU - Lingas, Andrzej

AU - Pagh, Rasmus

AU - Tokuyama, Takeshi

N1 - Funding Information: We thank anonymous referees for helping us to improve preliminary versions of this paper. Christos Levcopoulos and Andrzej Lingas were supported in part by Swedish Research Council Grant 621-2011-6179. Takeshi Tokuyama was supported by JSPS Grant Scientific Research (B) 15H02665, JSPS Scientific Research for Innovative Area 24106007, and JST ERATO Kawarabayashi Big-Graph Project. Publisher Copyright: © 2016, The Author(s).

PY - 2017/10/1

Y1 - 2017/10/1

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 O~ (n2+ kn) time and a deterministic O~ (kn2) -time algorithm for this problem (where the notation O~ 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 O~ (n2+ kn) time and a deterministic O~ (kn2) -time algorithm for this problem (where the notation O~ suppresses polylogarithmic terms in n and k).

KW - Matrix multiplication

KW - Matrix product correction

KW - Matrix product verification

KW - Randomized algorithms

KW - Time complexity

UR - http://www.scopus.com/inward/record.url?scp=84983032223&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84983032223&partnerID=8YFLogxK

U2 - 10.1007/s00453-016-0202-3

DO - 10.1007/s00453-016-0202-3

M3 - Article

AN - SCOPUS:84983032223

SN - 0178-4617

VL - 79

SP - 428

EP - 443

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -

Efficiently Correcting Matrix Products

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this