Efficiently Correcting Matrix Products

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

University of Liverpool
,
Lund University
,
Algorithms
,
Tohoku University

Research Output:

Journal Article or Conference Article in Journal

Journal article

Peer-review

Open access

Publication Information

Output type

Research Output:

Journal Article or Conference Article in Journal

Journal article

Peer-review

Original language

English

Pages from-to (Number of pages)

Pages 1-16

Journal (Volume, Issue Number)

Algorithmica

Publication milestones

Published - 22/08/2016

Publication status

Published - 22/08/2016

ISSN

0178-4617

Publication IDs

Scopus: 84983032223

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).

Publication metrics

PlumX, opens in new tab

Citations

Captures

Access to documents

10.1007/s00453-016-0202-3

210583dcf7d6eb50d1c9aa65099011e66b17

Accepted author manuscript, 330.13 KB

License:CC BY

10.1007_s00453_016_0202_3

Final published version, 2.81 MB

License:CC BY