Sparse Matrix Multiplication Exponent 1.5 in the Low-bandwidth Model

Get email updates

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.

What was already known

The earlier supported-model bounds over fields were O(d1.907)O(d^{1.907}) and O(d1.832)O(d^{1.832}). Using a newer centralised multiplication exponent in the latter framework would give O(d1.82223)O(d^{1.82223}).

AI involvement AI-led

The authors credit OpenAI models, primarily GPT-6, with the algorithm design. They name GPT-6 Astra and GPT-6.1 Sol among the tools used for the design, proof and Lean work.

Importance Notable

Clustering dense rectangles of requested output positions lets the algorithm handle those blocks and the sparse remainder separately. The improvement works over semirings and does not use fast centralised matrix multiplication.

Technical verification Reported

The authors link a Lean formalization. The archive could not be inspected to establish the exact checked theorem and a completed run.

Human understanding Explained

The authors explain the algorithm in the paper, including why removing dense output rectangles bounds the communication needed for the remaining products.

Correction and publication history