Efficiently Correcting Matrix Products

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

• Författare: Leszek Gasieniec; Christos Levcopoulos; Andrzej Lingas
• Avdelning/ar: Institutionen för datavetenskap; Parallella System
• Publiceringsår: 2014
• Språk: Engelska
• Sidor: 53-64
• Publikation/Tidskrift/Serie: Algorithms and Computation, ISAAC 2014
• Volym: 8889
• Länkar: http://dx.doi.org/10.1007/978-3-319-13075-0_5
• Dokumenttyp: Konferensbidrag
• Förlag: Springer
• Ämne: Computer Science
• Nyckelord: 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/Övrigt: ISSN: 1611-3349; ISSN: 0302-9743