2026-07-22T00:14:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24395 2025-12-12T15:01:27Z ddc:004 open_access

A Simplified Reduction for Error Correcting Matrix Multiplication Algorithms Shinkar, Igor Singh, Harsimran Matrix Multiplication Reductions Worst case to average case reductions We study the problem of transforming an algorithm for matrix multiplication, whose output has a small fraction of the entries correct into a matrix multiplication algorithm, whose output is fully correct for all inputs. In this work, we provide a new and simple way to transform an average-case algorithm that takes two matrices A,B ∈ 𝔽_p^{n×n} for a prime p, and outputs a matrix that agrees with the matrix product AB on a 1/p + ε fraction of entries on average for a small ε > 0, into a worst-case algorithm that correctly computes the matrix product for all possible inputs. Our reduction employs list-decodable codes to transform an average-case algorithm into an algorithm with one-sided error, which are known to admit efficient reductions from the work of Gola, Shinkar, and Singh [Gola et al., 2024]. Our reduction is more concise and straightforward compared to the recent work of Hirahara and Shimizu [Hirahara and Shimizu, 2025], and improves the overhead in the running time incurred during the reduction. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Igor Shinkar and Harsimran Singh 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.29 urn:nbn:de:0030-drops-243953 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.29 eng https://creativecommons.org/licenses/by/4.0/legalcode