Efficiently correcting matrix products

DOI10.1007/978-3-319-13075-0_5MaRDI QIDQ2942613zbMATH OpenOpenAlexFDO

Authors Leszek Gąsieniec, Christos Levcopoulos, Andrzej Lingas

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.00435, https://lup.lub.lu.se/record/07ff6fdc-af95-4109-b547-76926cf9c896

zbMATH Keywords

correction algorithmsmatrix multiplicationmatrix product verificationrandomized algorithms

Mathematics Subject Classification ID

Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40)

Abstract: We study the problem of efficiently correcting an erroneous product of two $nimesn$ 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 $ildeO(n^2+kn)$ time and a deterministic $ildeO(k{n}^2)$-time algorithm for this problem (where the notation $ildeO$ suppresses polylogarithmic terms in $n$ and $k$).

Recommendations

• Efficiently correcting matrix products
• Error correction in fast matrix multiplication and inverse
• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• Highly resilient correctors for polynomials
• LU factorization with errors

Cites work

• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• Certifying algorithms
• Deterministic verification of integer matrix multiplication in quadratic time
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 3573787 (Why is no real title available?)
• scientific article; zbMATH DE number 1559535 (Why is no real title available?)
• scientific article; zbMATH DE number 823957 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• Multiplying matrices faster than coppersmith-winograd
• Optimal Two-Stage Algorithms for Group Testing Problems
• Powers of tensors and fast matrix multiplication
• Quantum verification of matrix products
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Subcubic equivalences between path, matrix, and triangle problems

Cited in

(6)

• Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification
• Efficiently correcting matrix products
• Error‐free transformation of matrix multiplication with a posteriori validation
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• Error correction in fast matrix multiplication and inverse
• Correcting matrix products over the ring of integers

This page was built for publication: Efficiently correcting matrix products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942613)