Linear network codes for vector-linear network function computation over three-layer networks
2026-08-03 • Information Theory
Information Theory
AI summaryⓘ
The authors study how to compute functions using linear methods in a specific kind of three-layer network with fixed rules about which sources can be accessed. They develop a mathematical way to represent the problem as a global space made from rows meeting local network constraints, and prove this matches the existence of a workable linear code. They find exact conditions for when such codes can be built and how much communication is needed between parts of the network. Their approach separates the problem into local and global parts and helps describe the capacity for linear computation, which they then apply to special cases called MDS targets in cyclic networks, determining capacity in various scenarios.
vector-linear function computationthree-layer networkssupport-constrained row spacelinear computing codelocal support-constraintsglobal row spaceMDS codesnetwork coding capacitycut-set boundcyclic networks
Authors
Min Xu, Gennian Ge
Abstract
We study vector-linear function computation over three-layer networks with a fixed target function and a fixed source-access pattern. We develop a support-constrained row-space framework that represents a linear computing code by a global row space. This space must contain the target row space and be generated by rows satisfying the local support-constraints of the network. We prove that this representation is equivalent to the existence of a linear computing code. For any prescribed global row space, we give a necessary and sufficient condition for its realization and determine the minimum uniform communication load at the middle nodes. The condition is expressed in terms of the ranks of the local subspaces supported on the source-access sets. It separates the exact local realization problem from the outer problem of designing the global row space and yields a variational characterization of the linear computing capacity. We then apply the framework to MDS targets over cyclic networks. We identify when the target row space alone is sufficient and when auxiliary rows are required. We determine the capacity in the dense regime and in the sparse regime whenever the cut-set bound is integral. For the remaining sparse parameters, we give a general linear construction whose achievable rate equals the integer part of the cut-set bound.