# Optimal Deterministic Fully Sparse Matrix Multiplication

Preprint · Omar Graia

- Archive id: arxiv:2608.18496
- Published: 2026-08-19
- arXiv: https://arxiv.org/abs/2608.18496
- Source URL: https://arxiv.org/abs/2608.18496
- PDF: https://arxiv.org/pdf/2608.18496
- Provenance: arxiv

## Abstract

We give the first deterministic algorithm for fully sparse matrix multiplication that attains the optimal running-time exponent. This result matches the best previously known randomized algorithm running-time exponent. Given compatible matrices $A$ and $B$ over an arbitrary associative ring with identity, with $\\operatorname{nnz}(A),\\operatorname{nnz}(B)=O(n^{δ\_{\\mathrm{in}}})$ and $\\operatorname{nnz}(AB)=O(n^{δ\_{\\mathrm{out}}})$, our algorithm finds the support of $AB$ and computes the product exactly in $$O\\!\\left(n^{β\_R(δ\_{\\mathrm{in}},\\min\\{δ\_{\\mathrm{out}},2δ\_{\\mathrm{in}}\\})+\\varepsilon}\\right)$$ operations, where $β\_R(δ\_{\\mathrm{in}},δ)$ denotes the maximum of $δ\_{\\mathrm{in}}$ and $ω\_{δ\_{\\mathrm{in}},R}(a,1,b)$ over all $a,b\\in\[0,1\]$ satisfying $a+b=δ$. For dense inputs over a commutative ring, this bound simplifies to $O(n^{ω\_R((δ\_{\\mathrm{out}}-1)\_+,1,1)+\\varepsilon})$. With the current rectangular matrix multiplication bounds, this is nearly quadratic, namely $O(n^{2+\\varepsilon})$, for every $δ\_\\mathrm{out}\\le1.321334$, improving the previous deterministic range of $δ\_{\\mathrm{out}}\\le 0.642668$. To prove this result, we develop a general deterministic recovery technique that finds and fixes sparse parts of an unknown matrix while keeping temporary errors in denser parts under control.

_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.