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 nonlinear transformations of A and B, carefully calibrated to work synergistically with the structured linear encoding scheme by K¨orner and Marton. The subsequent converses derived here, calibrate the Han-Kobayashi approach and the strong converse of Ahlswede-G´acs-K¨orner 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.