dorsal/arxiv
View SchemaFundamental Limits of Multi-User Distributed Computing of Linearly Separable Functions
| Authors | K. K. Krishnan Namboodiri, Elizabath Peter, Derya Malak, Petros Elia |
|---|---|
| Categories | |
| ArXiv ID | 2601.10603vv1 |
| URL | https://arxiv.org/abs/2601.10603 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
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 $L$ users, each requesting a linearly separable function over $K$ basis subfunctions from a master node, who is assisted by $N$ distributed servers. At the core of this problem lies a fundamental tradeoff between communication and computation: each server can compute up to $M$ subfunctions, and each server can communicate linear combinations of their locally computed subfunctions outputs to at most $\Delta$ 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 $K$, $L$, $M$, and $\Delta$, 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.
{
"annotation_id": "9bb400cd-72ad-4c52-b9cc-afe294d429c6",
"date_created": "2026-02-17T05:53:24.321000Z",
"date_modified": "2026-02-17T05:53:24.321000Z",
"file_hash": "6341cb2418b008b18fd400bf59a701f9258e0450642f4d2dd3386ef1490f479a",
"private": false,
"record": {
"abstract": "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 $L$ users, each requesting a linearly separable function over $K$ basis subfunctions from a master node, who is assisted by $N$ distributed servers. At the core of this problem lies a fundamental tradeoff between communication and computation: each server can compute up to $M$ subfunctions, and each server can communicate linear combinations of their locally computed subfunctions outputs to at most $\\Delta$ 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 $K$, $L$, $M$, and $\\Delta$, 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.",
"arxiv_id": "2601.10603",
"authors": [
"K. K. Krishnan Namboodiri",
"Elizabath Peter",
"Derya Malak",
"Petros Elia"
],
"categories": [
"cs.IT",
"math.IT"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Fundamental Limits of Multi-User Distributed Computing of Linearly Separable Functions",
"url": "https://arxiv.org/abs/2601.10603",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d11386de-3b44-426c-afdf-d7307c33ad6b",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}