Sparse matrix multiplication with limited communication

Suppose n computers hold the entries of two sparse matrices and must compute selected entries of their product. Each computer can send and receive one short message per round. How many rounds are needed when each input row, input column and requested output row or column contains at most d positions?

Why it matters and what counts as progress

Why it matters: In distributed computation, the slow part can be moving values to the machines that need them. The round count measures how well an algorithm uses that communication budget.

What counts as progress: Give a faster round bound or a lower bound in the same communication model. Specify which input and output positions are known in advance, how entries are distributed and which arithmetic operations fit in a message.

How the problem developed

  1. 2022 · Earlier round bound [3]

    Chetan Gupta and collaborators Gave a subquadratic round bound for supported sparse multiplication over fields.

  2. 11 Nov 2026 · Faster algorithm [1]

    Chetan Gupta, Jukka Suomela and Hossein Vahidi with GPT-6 Reported a deterministic round exponent of 3/2 in the supported model over semirings.

AI contribution

Sparse Matrix Multiplication Exponent 1.5 in the Low-bandwidth Model

Chetan Gupta, Jukka Suomela, Hossein Vahidi

For uniformly sparse inputs and a uniformly sparse output mask with at most d positions per row and column, Gupta, Suomela and Vahidi give a deterministic O(d3/2)O(d^{3/2})-round algorithm. It works with globally known masks, balanced input and output distribution, and semiring values that fit in O(log⁡n)O(\log n) bits.

AI involvementAI-led
ImportanceNotable
Technical verificationReported
Human understandingExplained
Paper date:

Sources

  1. Gupta, Suomela and Vahidi’s sparse multiplication algorithm
  2. Lean formalization archive
  3. Sparse Matrix Multiplication in the Low-Bandwidth Model
Publication history