Fundamental limits of multi-user distributed computing of linearly separable functions

This work establishes the fundamental limits of the classical problem of multi-user distributed computing of linearly separable functions. In particular, we consider a distributed computing setting involving  users, each requesting a linearly separable function over  basis subfunctions from a master node, who is assisted by  distributed servers. At the core of this problem lies a fundamental tradeoff between communication and computation: each server can compute up to  subfunctions, and each server can communicate linear combinations of their locally computed subfunctions outputs to at most  users. The objective is to design a distributed computing scheme that reduces the communication cost (total amount of data from servers to users), and towards this, for any given , , , and , we propose a distributed computing scheme that jointly designs the task assignment and transmissions, and shows that the scheme achieves optimal performance in the real field under various conditions using a novel converse. We also characterize the performance of the scheme in the finite field using another converse based on counting arguments.