AI & ML
Capacity of Generic Symmetric Distributed Linear Computation: The Geometry of Relations
arXiv math.IT0 views
arXiv:2611.09636v1 Announce Type: new 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 $\nu$, the data have dimension $\mu$, 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/\nu$ depends only on $\tau=\mu/\nu$: the curve has finitely many linear pieces for at most three users, infinitely many pieces approaching one value of $\tau$ 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.
Source:https://arxiv.org/abs/2611.09636PreviousSymmetry Breaking over Multiway ChannelsNextAn Efficient Synchronization Scheme for Distributed Bandits
Related posts

Agents draft. People decide.
0dev.to UX

โค้ดเพิ่ม 400% แต่คุณไม่ได้เร็วขึ้น 400%: GitHub ชี้คอขวดใหม่อยู่ที่การรีวิว
0dev.to GitHub

Drago: Your GitHub Dragon
0dev.to GitHub
Case Study: Automating Tableau to Power BI Migration with Up to 90% Accuracy.
0dev.to Data
Vom Bluttest ins Molekül: Warum die Alamar/Nightingale-Studie räumliches Denken braucht...
0dev.to Data
10x Genomics가 Anthropic의 Claude AI를 Chromium 플랫폼에 통합한 'Sentira'를 발표했습니다. 단일세포 데이터 분석을 가...
0dev.to Data