Structured Codes for Distributed Matrix Multiplication
IEEE Transactions on Information Theory · 2026-07 · 72 (7) · 5160-5182
DOI: 10.1109/tit.2026.3692427 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-07. Verfasst von Derya Malak. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Gefördert von: European Research Council ERC-StG Project SENSIBILITÉ, Huawei France-Funded Chair Toward Future Wireless Networks, Program “PEPR Networks of the Future” of France 2030.
Abstract (Originalsprache)
Our work addresses the well-known open problem of distributed computing of bilinear functions of two correlated sources A and B . In a setting with two nodes, with the first node having access to A and the second to B , we establish bounds on the optimal sum rate that allows a receiver to compute an important class of non-linear functions, and in particular bilinear functions, including dot products $\langle {\mathbf { A}},{\mathbf { B}}\rangle $ , and general matrix products ${\mathbf { A}}^{\intercal }{\mathbf { B}}$ over finite fields. The bounds are tight for large field sizes, for which case we can derive the exact fundamental performance limits for all problem dimensions and a large class of sources. Our achievability scheme involves the design of non-linear transformations of A and B , carefully calibrated to work synergistically with the structured linear encoding scheme by Körner and Marton. The subsequent converses derived here, calibrate the Han-Kobayashi approach and the strong converse of Ahlswede-Gács-Körner to yield relatively tight converses on the sum rate. We exhibit unbounded compression gains over Slepian-Wolf coding, depending on the source correlations. In the end, this work characterizes the fundamental limits of distributed computing for a crucial class of functions, while succinctly capturing the inherent computation structures and source correlations.
Förderung
- European Research Council ERC-StG Project SENSIBILITÉ
- Huawei France-Funded Chair Toward Future Wireless Networks
- Program “PEPR Networks of the Future” of France 2030
Zitieren
APA
Malak, D. (2026). Structured Codes for Distributed Matrix Multiplication. IEEE Transactions on Information Theory, 72(7), 5160-5182. https://doi.org/10.1109/tit.2026.3692427
Vancouver
Malak D. Structured Codes for Distributed Matrix Multiplication. IEEE Transactions on Information Theory. 2026;72(7):5160-5182. doi:10.1109/tit.2026.3692427
BibTeX
@article{Malak2026,
author = {Malak, Derya},
title = {Structured Codes for Distributed Matrix Multiplication},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {7},
pages = {5160--5182},
doi = {10.1109/tit.2026.3692427}
}
EUVIMED