The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Efficiently Correcting Matrix Products

På svenska

Author

Summary, in English

We study the problem of efficiently correcting an erroneous product of two n x n matrices over a ring. We provide a randomized algorithm for correcting a matrix product with k erroneous entries running in (O) over tilde(root kn(2)) time and a deterministic (O) over tilde (kn(2))-time algorithm for this problem (where the notation (O) over tilde suppresses polylogarithmic terms in n and k).

Publishing year

2014

Language

English

Pages

53-64

Publication/Series

Algorithms and Computation, ISAAC 2014

Volume

8889

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Keywords

  • Matrix multiplication
  • Matrix product verification
  • Correction
  • algorithms
  • Randomized algorithms

Conference name

25th International Symposium on Algorithms and Computation (ISAAC), 2014

Conference date

2014-12-15 - 2014-12-17

Conference place

Jeonju, Korea, Republic of

Status

Published

ISBN/ISSN/Other

  • ISSN: 1611-3349
  • ISSN: 0302-9743