Derya Malak

Derya Malak

Our work addresses the well-known open problem of distributed computing of bilinear functions of two correlated sources ${\bf A}$ and ${\bf B}$. In a setting with two nodes, with the first node having access to ${\bf A}$ and the second to ${\bf 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 {\bf A},{\bf B}\rangle$, and general matrix products ${\bf A}^{\intercal}{\bf 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 ${\bf A}$ and ${\bf 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.

Ali Khalesi, Ahmad Tanha, Derya Malak et al.

This paper considers an $N$-server distributed computing setting with $K$ users requesting functions that are arbitrary multivariable polynomial evaluations of $L$ real (potentially non-linear) basis subfunctions, where each function output is raised to a bounded power. Our aim is to seek efficient task allocation and data communication techniques that reduce computation and communication costs. To this end, we take a tensor-theoretic approach, in which we represent the requested non-linearly decomposable functions using a properly designed tensor $\bar{\mathcal{F}}$, whose sparse decomposition into a tensor $\bar{\mathcal{E}}$ and a matrix $\mathbf{D}$ directly defines the task assignment, connectivity, and communication patterns. We design a lossless achievable scheme that integrates fixed-support SVD-based tensor factorization with multi-dimensional tiling of $\bar{\mathcal{E}}$ and $\mathbf{D}$, followed by a bipartite graph matching-based recursive assignment of tiles. This step transforms an overlapping decomposition into a disjoint one and reduces the resulting sum rank of the tiles, thereby decreasing the number of required servers. Under mild dimensionality conditions, we derive an explicit zero-error characterization of the achievable system rate $K/N$. Numerical simulations demonstrate the computational and communication savings over existing state-of-the-art matrix factorization approaches across a wide range of system parameters.