Capacity of Generic Symmetric Distributed Linear Computation: The Geometry of Relations
Abstract
In distributed linear computation, K users observe linear functions of common finite-field data and send separate messages to a server that wants another linear function. We characterize the generic capacity C, the minimum total number of field symbols sent per computed instance, when all observations and the demand have dimension ν, the data have dimension μ, and the coefficients of these linear functions are drawn independently and uniformly from the field and stay fixed during coding, with the field size growing through arbitrary prime powers. For fixed K, C/ν depends only on τ=μ/ν: the curve has finitely many linear pieces for at most three users, infinitely many pieces approaching one value of τ for four users, and a rational part between two sequences of linear pieces for five or more users. The geometry of the relation space, formed by the linear relations among the observations and the demand, determines three things: the shape of the curve, which relations the coding scheme aligns, and the entropy inequalities used in the converse. Generically, the user subspaces of this space are either balanced, where the capacity lies on a single rational curve, or split into two balanced components, a sparse and a dense one, which produces the linear pieces. Achievability uses asymptotic set alignment, in which monomial precoders confine the combined observation differences to a small set. The converse uses the same geometry to lower-bound the sum of the users' remaining observation entropies in terms of the remaining data entropy.
Related
- Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio
- Privacy-Constrained Function Computation in Distributed Databases
- Deterministic Distributed Linearly Separable Computation via Nested Cyclic Codes
- On the generation of the symmetric group by index relations of three prefix reversals
- An information-geometric formulation of distributed computation
BibTeX
@misc{sun2026capacity,
title = {{Capacity of Generic Symmetric Distributed Linear Computation: The Geometry of Relations}},
author = {Hua Sun},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.09636},
eprint = {2611.09636},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.09636},
}
RIS
TY - UNPB
TI - Capacity of Generic Symmetric Distributed Linear Computation: The Geometry of Relations
AU - Hua Sun
PY - 2026
DA - 2026/11/06
PB - arXiv
DO - 10.48550/arxiv.2611.09636
UR - https://arxiv.org/abs/2611.09636
AB - In distributed linear computation, K users observe linear functions of common finite-field data and send separate messages to a server that wants another linear function. We characterize the generic capacity C, the minimum total number of field symbols sent per computed instance, when all observations and the demand have dimension ν, the data have dimension μ, and the coefficients of these linear functions are drawn independently and uniformly from the field and stay fixed during coding, with the field size growing through arbitrary prime powers. For fixed K, C/ν depends only on τ=μ/ν: the curve has finitely many linear pieces for at most three users, infinitely many pieces approaching one value of τ for four users, and a rational part between two sequences of linear pieces for five or more users. The geometry of the relation space, formed by the linear relations among the observations and the demand, determines three things: the shape of the curve, which relations the coding scheme aligns, and the entropy inequalities used in the converse. Generically, the user subspaces of this space are either balanced, where the capacity lies on a single rational curve, or split into two balanced components, a sparse and a dense one, which produces the linear pieces. Achievability uses asymptotic set alignment, in which monomial precoders confine the combined observation differences to a small set. The converse uses the same geometry to lower-bound the sum of the users' remaining observation entropies in terms of the remaining data entropy.
ER -