2025/10/21 by Mark Braverman, Zhou He, Braverman, Mark +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Information Theory (cs.IT) #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.2510.18737
openalex publication_date 2025/10/21 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
The network coding problem asks whether data throughput in a network can be increased using coding (compared to treating bits as commodities in a flow). While it is well-known that a network coding advantage exists in directed graphs, the situation in undirected graphs is much less understood -- in particular, despite significant effort, it is not even known whether network coding is helpful at all for unicast sessions. In this paper we study the multi-source multicast network coding problem in undirected graphs. There are k sources broadcasting each to a subset of nodes in a graph of size n. The corresponding combinatorial problem is a version of the Steiner tree packing problem, and the network coding question asks whether the multicast coding rate exceeds the tree-packing rate. We give the first super-constant bound to this problem, demonstrating an example with a coding advantage of Ω(log k). In terms of graph size, we obtain a lower bound of 2Ω(√(log log n)). We also obtain an upper bound of O(log n) on the gap. Our main technical contribution is a new reduction that converts locally-decodable codes in the low-error regime into multicast coding instances. This gives rise to a new family of explicitly constructed graphs, which may have other applications.