Papers for
network coding developers
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Capacity limits found for distributed linear computations over fields
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.
Capacity limits for distributed linear computation depend on subspace cross-ratio
Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio
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.
Sum rank Reed Muller style codes unify and generalize known code families
Sum-rank analogues of Reed--Muller codes over Abelian Galois extensions
Abstract: Let $\mathbb L/\mathbb K$ be a finite Abelian Galois extension with a fixed decomposition $\mathrm{Gal}(\mathbb L/\mathbb K)=\langleσ_1\rangle\times\cdots\times\langleσ_m\rangle$. We show that the quotient of the multivariate skew polynomial ring $\mathbb L[x_1,\ldots,x_m;σ_1,\ldots,σ_m]$ by suitable central polynomials $H_1(x_1),\ldots,H_m(x_m)$ is isomorphic to a product of $t$ copies of $\mathrm{End}_{\mathbb K}(\mathbb L)$, so that one skew polynomial represents all blocks of a sum-rank metric space. The sum-rank weight of an element equals the rank of an associated Dickson matrix and of a generalized Moore matrix. Using this, we define sum-rank Reed--Muller-type codes and show that their dimension and minimum distance are given by the formulas for affine Cartesian codes with side lengths $\mathrm{deg}\,H_1,\ldots,\mathrm{deg}\,H_m$; the same holds for codes supported on lower sets. The family contains as special cases linearized Reed--Solomon codes, Gabidulin codes, rank-metric Reed--Muller codes, and affine Cartesian codes. Over finite fields, every linearized Reed--Muller code of Berardini and Caruso is, after a monomial change of variables, a monomial code in our framework. This gives the dimension of all these codes, and their exact minimum distance in every degree whenever the support is a lower set.
Construction of new error correcting codes from special field extensions
On MRD constacyclic codes over inseparable field extensions
Abstract: In this paper, we construct MRD constacyclic codes of length $p$ over an inseparable field extension $L/K$, where $K$ has characteristic $p$. In particular, these codes cannot be obtained from known constructions.
Simple proof links group theory to advanced entropy inequalities
A simple proof of the group-theoretic Zhang-Yeung inequality
Abstract: Zhang and Yeung (IEEE Trans. Inf. Theory, 1998) established the first non-Shannon-type inequality that holds for all entropic vectors. Chan and Yeung (IEEE Trans. Inf. Theory, 2002) showed that there is a one-to-one relation between linear entropy inequalities and multiplicative inequalities involving cardinalities of subgroups of a finite group. The Shannon inequality admits a simple proof in the group theoretic setting, but a direct proof of the translation of Zhang--Yeung's inequality to the group-theoretic setting remained elusive. We resolve this open problem, giving a direct proof of the group-theoretic Zhang--Yeung inequality for cardinalities of subgroups of finite groups, using elementary group-theoretic and counting arguments.