Multi-User Linearly Separable Computation: A Coding Theoretic Approach

In this work, we investigate the problem of multi-user linearly separable function computation, where N servers help compute the desired functions (jobs) of K users. In this setting each desired function can be written as a linear combination of up to L (generally non-linear) sub-functions. Each server computes some of the sub-tasks, and communicates a linear combination of its computed outputs (files) in a single-shot to some of the users, then each user linearly combines its received data in order to recover its desired function. We explore the range of the optimal computation cost via establishing a novel relationship between our problem, syndrome decoding and covering codes. The work reveals that in the limit of large N, the optimal computation cost — in the form of the maximum fraction of all servers that must compute any subfunction — is lower bounded as $\gamma \geq H_q^{ - 1}\left( {\frac{{{{\log }_q}(L)}}{N}} \right)$, for any fixed log
q
(L)/N. The result reveals the role of the computational rate log
q
(L)/N, which cannot exceed what one might call the computational capacity H
q
(γ) of the system.