Efficiently Correcting Matrix Products

DOI10.1007/978-3-319-13075-0_5zbMath1370.68336arXiv1602.00435OpenAlexW1690582634MaRDI QIDQ2942613

Leszek Gąsieniec, Andrzej Lingas, Christos Levcopoulos

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

zbMATH Keywords

randomized algorithmsmatrix multiplicationcorrection algorithmsmatrix product verification

Mathematics Subject Classification ID

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

Related Items (1)

Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification

Cites Work

• Certifying algorithms
• Matrix multiplication via arithmetic progressions
• A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits
• Gaussian elimination is not optimal
• Deterministic Verification of Integer Matrix Multiplication in Quadratic Time
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Powers of tensors and fast matrix multiplication
• Quantum verification of matrix products
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Optimal Two-Stage Algorithms for Group Testing Problems
• Multiplying matrices faster than coppersmith-winograd
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficiently Correcting Matrix Products