Undirected Multicast Network Coding Gaps via Locally Decodable Codes

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 Ω(sqrt 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.