# Matrix Multiplication Reductions

Preprint · Ashish Gola, Igor Shinkar, Harsimran Singh

- Archive id: arxiv:2404.08085
- Published: 2024-04-11
- arXiv: https://arxiv.org/abs/2404.08085
- Source URL: https://arxiv.org/abs/2404.08085
- PDF: https://arxiv.org/pdf/2404.08085
- Provenance: arxiv

## Abstract

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 \\cdot 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. (1) 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. (2) One-sided error in the low agreement regime: Focusing on average case algorithms with one-sided error, we show that over $\\mathbb{F}\_2$ 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 \\cdot B$ on at least $51\\%$ of the entries (i.e., has only a slight advantage over the trivial algorithm), and transforms it into an $\\widetilde{O}(T)$ time worst case algorithm, that outputs the correct answer for all inputs with high probability.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.