New Achievability Schemes for Distributed Computing of Linearly Separable Functions

This work addresses the classical problem of distributed computation of linearly separable functions, where a master node with access to K datasets employs N servers to compute L user-requested functions, each defined over the datasets. Servers are assigned subfunctions of the datasets and transmit computed outputs to the user, who reconstructs the demanded outputs. The central challenge is to minimize both the per-server computational load and the communication cost from servers to the user, while ensuring recovery for any possible set of L demands. For any given K, L, and M , we propose a distributed computing scheme that achieves the optimal communication cost when K < L + M . When M ≥ K/2, we present an alternative scheme that yields a lower communication cost than the former. The key innovation in both schemes is a nullspacebased design principle that governs both dataset assignment and server transmissions, ensuring exact decodability for all demands.