Computing linear functions by linear coding over networks

2011/02/23 by Rathinakumar Appuswamy, Massimo Franceschetti, Appuswamy, Rathinakumar +1 · 5 citations
Computer Science · Mathematics · #Commutative Algebra (math.AC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #cs.IT #math.AC #math.IT

paper · pdf · doi:10.48550/arxiv.1102.4825

arxiv created 2011/02/23 · arxiv updated 2011/02/24

Abstract

We consider the scenario in which a set of sources generate messages in a network and a receiver node demands an arbitrary linear function of these messages. We formulate an algebraic test to determine whether an arbitrary network can compute linear functions using linear codes. We identify a class of linear functions that can be computed using linear codes in every network that satisfies a natural cut-based condition. Conversely, for another class of linear functions, we show that the cut-based condition does not guarantee the existence of a linear coding solution. For linear functions over the binary field, the two classes are complements of each other.

Cited by

• On hierarchical secure aggregation against relay and user collusion
• Uniquely-Decodable Coding for Zero-Error Network Function Computation
• Distributed Source Coding for Compressing Vector-Linear Functions
• Linear network codes for vector-linear network function computation over three-layer networks
• Secure Network Function Computation for Linear Functions, Part II: Target-Function Security

Related

• Linear Codes, Target Function Classes, and Network Computing Capacity
• Linear Network Coding for Robust Function Computation and Its Applications in Distributed Computing
• Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability
• Linear Network Coding: Effects of Varying the Message Dimension on the Set of Characteristics
• Constrained Linear Representability of Polymatroids and Algorithms for Computing Achievability Proofs in Network Coding