2026-08-03T09:27:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21027 2024-09-16T06:02:38Z ddc:004 open_access

Matrix Multiplication Reductions Gola, Ashish Shinkar, Igor Singh, Harsimran Matrix Multiplication Reductions Worst case to average case reductions In this paper we study a worst case to average case reduction for the problem of matrix multiplication over finite fields. Suppose we have an efficient average case algorithm, that given two random matrices A,B outputs a matrix that has a non-trivial correlation with their product A ⋅ B. Can we transform it into a worst case algorithm, that outputs the correct answer for all inputs without incurring a significant overhead in the running time? We present two results in this direction. - Two-sided error in the high agreement regime. We begin with a brief remark about a reduction for high agreement algorithms, i.e., an algorithm which agrees with the correct output on a large (say > 0.9) fraction of entries, and show that the standard self-correction of linearity allows us to transform such algorithms into algorithms that work in worst case. - One-sided error in the low agreement regime. Focusing on average case algorithms with one-sided error, we show that over 𝔽₂ there is a reduction that gets an O(T) time average case algorithm that given a random input A,B outputs a matrix that agrees with A ⋅ B on at least 51% of the entries (i.e., has only a slight advantage over the trivial algorithm), and transforms it into an Õ(T) time worst case algorithm, that outputs the correct answer for all inputs with high probability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ashish Gola and Igor Shinkar and Harsimran Singh 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.34 urn:nbn:de:0030-drops-210274 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.34 eng https://creativecommons.org/licenses/by/4.0/legalcode