{"ID":2852324,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.18737","arxiv_id":"2510.18737","title":"Undirected Multicast Network Coding Gaps via Locally Decodable Codes","abstract":"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^{\\tildeΩ(\\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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2510.18737","url_pdf":"https://arxiv.org/pdf/2510.18737v1","authors":"[\"Mark Braverman\",\"Zhongtian He\"]","published":"2025-10-21T15:39:49Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\",\"cs.IT\"]","methods":"[]","has_code":false}