跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

We study sparse matrix multiplication in the low-bandwidth model: nn computers multiply two n×nn\times n matrices, and each computer can send and receive one O(log⁡n)O(\log n)-bit message per round. The input matrices are uniformly sparse, meaning that there are at most dd 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 O(d1.907)O(d^{1.907})-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 O(d1.832)O(d^{1.832}) rounds. In this work, we give a deterministic algorithm that solves this problem in O(d3/2)O(d^{3/2}) rounds in the supported setting, improving the previous bounds over fields and semirings.

作者备注:Lean formalization available at https://doi.org/10.5281/zenodo.24127514

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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: nn computers multiply two n×nn\times n matrices, and each computer can send and receive one O(log⁡n)O(\log n)-bit message per round. The input matrices are uniformly sparse, meaning that there are at most dd 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 O(d1.907)O(d^{1.907})-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 O(d1.832)O(d^{1.832}) rounds. In this work, we give a deterministic algorithm that solves this problem in O(d3/2)O(d^{3/2}) rounds in the supported setting, improving the previous bounds over fields and semirings.

查看此版本解读 →查看此版本原文 ↗