Structured Codes for Distributed Matrix Multiplication

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 ⟨A, B⟩, and general matrix products A⊺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.