Undirected Multicast Network Coding Gaps via Locally Decodable Codes
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911224454709248 |
|---|---|
| author | Braverman, Mark He, Zhongtian |
| author_facet | Braverman, Mark He, Zhongtian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18737 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Undirected Multicast Network Coding Gaps via Locally Decodable Codes Braverman, Mark He, Zhongtian Computational Complexity Discrete Mathematics Data Structures and Algorithms Information Theory 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. |
| title | Undirected Multicast Network Coding Gaps via Locally Decodable Codes |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms Information Theory |
| url | https://arxiv.org/abs/2510.18737 |