Multi-user Linearly Separable Computation: A Coding Theoretic Approach

In this work, we investigate the problem of multiuser 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 singleshot

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   H−1 q (logq(L) N ), for any fixed logq(L)/N. The result reveals the role of the computational rate logq(L)/N, which cannot exceed what one might call the computational capacity Hq() of the system.