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: Contribution to journal › Article › peer-review

10 Scopus citations

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 (US)
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
State	Published - Oct 1 2017
Externally published	Yes

Keywords

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

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-016-0202-3

Cite this

@article{40a6e6dd18a845b1b759965e3c39dc1b,

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\textasciitilde{} (n2+ kn) time and a deterministic O\textasciitilde{} (kn2) -time algorithm for this problem (where the notation O\textasciitilde{} 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 = "Publisher Copyright: {\textcopyright} 2016, The Author(s).",

year = "2017",

month = oct,

day = "1",

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

language = "English (US)",

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

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 - https://www.scopus.com/pages/publications/84983032223

UR - https://www.scopus.com/pages/publications/84983032223#tab=citedBy

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