Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Efficiently Correcting Matrix Products

In English

Författare

Summary, in English

We study the problem of efficiently correcting an erroneous product of two n×n
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)
O~(n2+kn) time and a deterministic O~(kn2)
O~(kn2)-time algorithm for this problem (where the notation O~
O~suppresses polylogarithmic terms in n and k).

Publiceringsår

2017-10

Språk

Engelska

Sidor

428-443

Publikation/Tidskrift/Serie

Algorithmica

Volym

79

Issue

2

Dokumenttyp

Artikel i tidskrift

Förlag

Springer

Ämne

  • Computer Science

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0178-4617