← 研踪 PaperTrailarXiv:2611.15201 · v1
Sparse Matrix Multiplication Exponent 1.5 in the Low-bandwidth Model
首次提交 2026-11-11 16:49
版本更新 2026-11-11 16:49
雷达观测 2026-11-13 11:11
摘要
We study sparse matrix multiplication in the low-bandwidth model: computers multiply two matrices, and each computer can send and receive one -bit message per round. The input matrices are uniformly sparse, meaning that there are at most nonzero entries in each row and column, and the task is to compute a uniformly sparse part of their product. In prior work, Gupta et al.~(SPAA 2022) presented an -round algorithm over fields for this problem when the sparsity structure is globally known in advance (this is referred to as the supported setting). The upper bound was later improved to rounds. In this work, we give a deterministic algorithm that solves this problem in rounds in the supported setting, improving the previous bounds over fields and semirings.
作者备注:Lean formalization available at https://doi.org/10.5281/zenodo.24127514
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-11 16:49 · 最新观测版本
Sparse Matrix Multiplication Exponent 1.5 in the Low-bandwidth Model
We study sparse matrix multiplication in the low-bandwidth model: computers multiply two matrices, and each computer can send and receive one -bit message per round. The input matrices are uniformly sparse, meaning that there are at most nonzero entries in each row and column, and the task is to compute a uniformly sparse part of their product. In prior work, Gupta et al.~(SPAA 2022) presented an -round algorithm over fields for this problem when the sparsity structure is globally known in advance (this is referred to as the supported setting). The upper bound was later improved to rounds. In this work, we give a deterministic algorithm that solves this problem in rounds in the supported setting, improving the previous bounds over fields and semirings.
查看此版本解读 →查看此版本原文 ↗