CS Paper Radar

Capacity of Generic Symmetric Distributed Linear Computation: The Geometry of Relations

Hua Sun

cs.IT ·submitted 2026-11-06 15:51 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio

cs.IT ·2026-10-30 ·Hua Sun
similarity 0.74
Abstract

$K$ users each observe a fixed linear function of common data over a finite field of characteristic $p$, and a server must recover another fixed linear function with zero error from one message sent by each user. The capacity, the minimum total number of symbols the users send per computed instance, depends only on the configuration of subspaces formed by these linear functions. We study the instance in which three users observe $\boldsymbol{a}$, $\boldsymbol{b}$ and $\boldsymbol{a}+\boldsymbol{b}$ and the server wants $\boldsymbol{a}+λ\boldsymbol{b}$. The four functions span four lines in a plane with cross-ratio $λ$, the smallest instance of the four subspace problem of representation theory. It is the smallest configuration whose capacity is not determined by the dimensions of the subspaces formed by sums and intersections: these dimensions are the same for every $λ$, but the capacity depends on the cross-ratio and on the prime subfield. For the harmonic cross-ratios, $λ=-1$, $λ=2$ or $2λ=1$, it is $2$: every zero-error code reveals $(\boldsymbol{a},\boldsymbol{b})$ to the server, so no code beats having two users send their observations. For $λ$ outside the prime subfield it is the cut-set bound $3/2$, achieved by codes linear over the prime subfield, while codes linear over the field need $2$. For the other $λ$ in the prime subfield it lies in $[3p/(2p-1),2]$, so no code at any block length approaches the cut-set bound. The qualitative separation persists under vanishing error for uniform data: the cut-set bound is tight exactly for $λ$ outside the prime subfield. The four-line instance is also exact repair of one node of a $[4,2]$ MDS storage code, and the results translate to that setting.

0.56

Graph-Theoretic Bounds for Non-Linear Function Computation Broadcast

cs.IT ·2026-10-06 ·Derya Malak, Vijith Kumar K. P., M. Reza Deylam Salehi
publishedtheory similarity 0.60
Abstract · This work extends the conference version presented at IEEE ISIT 2025, available at https://arxiv.org/abs/2502.13688. Example 2, concerning t…

This work studies non-linear function computation broadcast (NFCB), in which a sender with access to $N$ datasets $(X_1,\dots,X_N)$ broadcasts a common message to $K$ users, each possessing side information and requesting a function of the datasets. The goal is to minimize the rate required for asymptotically lossless recovery of all demands. We introduce a broadcast graph that jointly captures the source distribution, side information, and demanded functions. Using Körner's characteristic-graph framework, we develop an achievable scheme for arbitrary $K$, general source distributions, and general finite-field demands, including linear, non-separable, and non-linear functions, without restricting the encoding or decoding operations to be linear. We also present a side-information-assisted independent-set scheme and characterize the optimal graph-based achievable rate for compatible functions. For the converse, we derive a multi-letter response-profile bound that strengthens a basic side-information converse, zero-error and asymptotically lossless clique-entropy bounds based on the operational block broadcast graph, and a genie-aided lower bound. For binary NFCB with $N=K$ and side information $X_i$ at user $i$, we characterize the optimal rate in several special cases and bound the worst-case and average additive gaps between the proposed achievable rate and the genie-aided converse for $K=3$ and $K=4$. Finally, three-user examples with Boolean and linear demands illustrate the proposed bounds and show that non-linear encoding can strictly outperform the best scalar and vector linear schemes.

0.48

Function Tables for Secure Distributed Matrix Multiplication

cs.IT ·2026-09-08 ·Rafael G. L. D'Oliveira, Giulia Gaggero, Arturo Jaramillo Gil, Hiram H. López, Cecilia Martínez-Reyes +1 more
theory similarity 0.58
Abstract

We introduce function tables, an entrywise representation of the coefficient functions that appear in the worker responses of a secure distributed matrix multiplication (SDMM) scheme. We work under the outer-product partition, with $K$ row blocks, $L$ column blocks, and privacy against any $T$ colluding workers, in the general model of linear encoding and linear decoding. In this representation, privacy is a rank condition on the data and mask coefficients, and decodability is linear independence of the desired entries modulo the nuisance space. Degree tables, cyclic-addition tables, and algebraic-geometry constructions are the special cases obtained by restricting the coefficient functions to a structured family; we impose no such restriction, so our converses bind every linear scheme. For $T=1$, we determine the exact optimum over every finite field $\mathbb{F}_q$: it is $KL+K+L$ when $q\geq3$, and $KL+K+L+1$ over $\mathbb{F}_2$, where the identity $z^2=z$ forces one more worker. For arbitrary $T$, we prove $N\geq KL+K+L$ and $N\geq\max\{K,L\}+T$ with no MDS hypothesis on the masks; the first is stronger than the previously known bound $KL+\max\{K,L\}+2T-1$ whenever $\min\{K,L\}\geq2T$. We then reduce field feasibility exactly to MDS existence: a scheme exists over $\mathbb{F}_q$ if and only if an $[\max\{K,L\}+T,T]$ linear MDS code does, and whenever it does, a Cartesian construction attains $N=(K+T)(L+T)$ over that same field. For $T=2$ this makes $q\geq\max\{K,L\}+1$ necessary and sufficient, and we give a projective-line construction with $N=KL+K+L+2$ whenever $KL+K+L$ divides $q-1$; for $K,L\geq2$ it matches the best known worker count while requiring only an element of order $KL+K+L$.

0.25

Bounds on the Service Rates of Linear Codes and their Connections to Combinatorial Designs

cs.IT ·2026-10-19 ·Monika Yadav, Priyanka Choudhary, Maheshanand Bhaintwal
theory similarity 0.58
Abstract

The service rate region of a distributed storage system describes the set of concurrent demand vectors that can be served without overloading any individual server, and is a fundamental measure of how effectively redundancy is used. In this paper, we investigate aggregate service rates in distributed data storage systems based on linear codes over arbitrary finite fields. We first derive an upper bound on the aggregate service rate for an arbitrary subset of $t$ data objects in terms of the dual distance and the sizes of their smallest recovery sets. For systematic generator matrices, this bound simplifies to an expression depending only on the code length, the dual distance, and the cardinality of the selected subset. This result extends existing bounds and provides a subset-wise formulation of the First Dual Distance Bound. We then establish conditions under which this upper bound is attained. We apply our results to several important families of linear codes, including MDS codes, Reed-Muller codes, constacyclic codes, and extended Golay codes, and obtain exact values of the maximum aggregate service rates for the corresponding subsets of data objects.

0.25

The Exact Memory-Rate Tradeoff for Three-User Secure Coded Caching

cs.IT ·2026-11-04 ·Han Fang, Nan Liu, Wei Kang
similarity 0.57
Abstract · 34 pages, 2 figures

We determine the exact zero-error memory-rate tradeoff for secure coded caching with three users and any number $N\ge2$ of independent files. Each user recovers its requested file, while its cache and the broadcast jointly reveal no information about the complete tuple of unrequested files. For $N\ge4$, two converse inequalities establish the optimality of the known achievable points and the memory-sharing segments between them. For $N=3$, two additional bounds identify a new corner at $(M,R)=(3/2,2)$, where memory and rate are measured in file units. An explicit linear code over $\mathbb{F}_3$ attains this corner and reduces the rate by one quarter of a file relative to memory sharing between the known points. The converse links the information held by cache pairs and triples to delivery under repeated and distinct requests. Its equality conditions guide the construction: users cancel the keys to recover their requested files, while uniform masking protects the complete tuple of unrequested files.

0.21

Deterministic Distributed Linearly Separable Computation via Nested Cyclic Codes

cs.IT ·2026-10-13 ·Anu Mathew, M. Nikhil Krishnan
similarity 0.57
Abstract · 13 pages, 1 figure

We study the $(K,N,S,M,K_c)$ distributed linearly separable computation (DLSC) setting, where a master employs $N$ workers with a per-worker computation load of $M$ to recover $K_c$ deterministic linear combinations of $K$ messages in the presence of up to $S$ stragglers. We propose a DLSC framework based on nested cyclic codes that achieves $M=\frac{K}{N}(S+K_c)$. For sufficiently large $K$, we establish the matching converse $M\geq\frac{K}{N}(S+K_c)$, proving the asymptotic computation load optimality of the proposed framework. By instantiating cyclic locally recoverable codes (LRCs) as base codes in the framework, the master can recover the desired $K_c$ linear combinations by contacting fewer than $N-S$ workers under many straggler scenarios. This essentially softens the straggler threshold without increasing the computation load or communication cost. Finally, we extend the construction to reduce the per-worker communication load by a factor of $m$, while achieving an asymptotically optimal computation load of $M=\frac{K}{N}(S+mK_c)$.

0.20

Information Spectrum Methods for MUltiple-Access Channels--Part III : The Strong Converse in the $K$-User Gaussian Case

cs.IT ·2026-11-12 ·Te Sun Han, Hideki Yagi
similarity 0.56
Abstract · 13 pages, 0 figures

This paper, Part III of a series, treats $K$-user multiple-access channels (MACs). Its starting point is a pair of fundamental lemmas, a random-coding lemma of Feinstein type and a converse lemma of Verdú--Han type, which are the $K$-user extensions of the two lemmas underlying Han's information spectrum approach to the general two-user MAC. From them we derive the capacity region of the general $K$-user MAC with cost constraint and show that it contains the polymatroid capacity region of the $K$-user Gaussian MAC. We then prove, by an elementary information spectrum calculation that adapts a diffuse--exceptional subspace decomposition used in recent second-order converses for the Gaussian MAC, that for every subset $\cS$ of users and every independent input satisfying the power constraints, the conditional information spectral-sup rate of the $K$-user Gaussian MAC does not exceed $\frac12\log(1+P_\cS/N)$, where $P_\cS$ is the total power of the users in $\cS$, with a probability bound that does not depend on the input. Consequently, the strong converse for the $K$-user Gaussian MAC, in the sense that the error probability tends to one for every rate tuple outside the capacity region, follows directly from the converse lemma, without the wringing technique and without hypothesis-testing meta-converses. This strong converse was first established by Fong and Tan, whose per-blocklength bounds yield it, through wringing and quantization. It is the key ingredient in the converse parts of the coding theorems for mixed Gaussian MACs in Part I, where the $\varepsilon$-strong converse would not suffice.

0.37

Breaking linearity in the sum-rank metric: MSRD codes from switched $σ$-rational normal curves

cs.IT math.CO ·2026-10-08 ·Daniele Bartoli, Giovanni Giuseppe Grimaldi, Giovanni Longobardi
similarity 0.55
Abstract

We construct a family of scalar-closed, non-additive maximum sum-rank distance codes (MSRD) by switching norm components of a $σ$-rational normal curve and lifting the resulting point set through a linearized Reed--Solomon syndrome map. We characterize the admissible switches by a multiplicative stability condition on the norm classes. In particular, for $1 \leq n_i \leq m$, $N=n_1+\ldots+n_{\ell}$ and $2\leqδ\leq N-1$, every partition of $\mathbb{F}_q^*$ satisfying a specific condition, referred to as Condition $(\diamond)$, yields a code in $\mathbb{F}_{q^m}^{N}$ of size $q^{m(N-δ+1)}$ and minimum sum-rank distance $δ$; the code is non-additive whenever a curve component is retained. For $\ell\geq2$ these appear to be the first non-additive MSRD codes in the literature, all previously known families with more than one block being $\mathbb{F}_q$-linear. Moreover, every code of the family has the same sum-rank weight distribution as an $\mathbb{F}_{q^m}$-linear MSRD code with the same parameters, although the geometry of the switched set distinguishes it from linearized Reed--Solomon codes. In the single-block case, an explicit rank isometry identifies the construction with the cone codes of Durante, Grimaldi and Longobardi.

0.36