2026-09-10T09:44:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27757 2026-09-09T12:19:37Z ddc:004 open_access

Output-Sparse Matrix Multiplication Using Compressed Sensing Bennett, Huck Gajulapalli, Karthik Golovnev, Alexander Warton, Evelyn Matrix Multiplication Sparse Matrices Compressed Sensing We give two algorithms for output-sparse matrix multiplication (OSMM), the problem of multiplying two n × n matrices A, B when their product AB is promised to have at most O(n^δ) many non-zero entries for a given value δ ∈ [0, 2]. We then show how to speed up these algorithms in the fully sparse matrix multiplication (FSMM) setting, where the input matrices A, B are themselves sparse. All of our algorithms work over arbitrary rings. Our first, deterministic algorithm for OSMM works via a two-pass reduction to compressed sensing. It runs in roughly n^{ω(δ/2, 1, 1)} time, where ω(⋅, ⋅, ⋅) is the rectangular matrix multiplication exponent. This substantially improves on prior deterministic algorithms for output-sparse matrix multiplication. Our second, randomized algorithm for OSMM works via a reduction to compressed sensing and a variant of matrix multiplication verification, and runs in roughly n^{ω(δ-1, 1, 1)} time. This algorithm and its extension to the fully sparse setting have running times that match those of the (randomized) algorithms for OSMM and FSMM, respectively, in recent work of Abboud, Bringmann, Fischer, and Künnemann (SODA, 2024). Our algorithm is quite simple when taking a suitable compressed sensing scheme as a black box. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Huck Bennett and Karthik Gajulapalli and Alexander Golovnev and Evelyn Warton 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.40 urn:nbn:de:0030-drops-277570 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.40 eng https://creativecommons.org/licenses/by/4.0/legalcode