Network coding outperforms traditional methods in undirected multiple unicast
The Multiple Unicast Conjecture is False
Information TheoryComputational ComplexityDiscrete MathematicsData Structures and Algorithms
Summary
The paper challenges a long-standing belief that network coding can't improve data flow in certain network settings. The authors built a special kind of communication setup that proves network coding can send more information simultaneously than standard routing methods. They used advanced math and computer tools to design and verify this example. This means network coding has more potential for improving how data travels in networks than previously thought.
What this means in practice
- •For network engineers: Design communication protocols that use network coding to increase throughput beyond traditional routing limits in undirected networks.
- •For distributed storage teams: Incorporate advanced coding schemes inspired by this work to improve data recovery and transfer efficiency in networked storage systems.
A theory result. No direct application yet.
Authors
Mark Braverman, Zhongtian He
Abstract
The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow. We refute this conjecture by constructing a deterministic linear network code over $\mathbb{F}_9$ on a 182-vertex bipartite subgraph of the point-line incidence graph of $\mathrm{PG}(2,9)$. The construction supports $157$ independent unicast sessions at common coding rate at least $1$, while every fractional multicommodity flow has common rate at most $147/157$. By the amplification theorem of~[BGS17], this yields a family of undirected multiple-unicast instances with coding gap $Ω((\log n)^\varepsilon)$ for some $\varepsilon>0$. We also introduce a nondeterministic model of network coding based on locally verifiable certificates, which guides our construction and may be of independent interest. Building on the high-girth graph and error-correcting code framework of [BH25], we use GPT-6 to find a nondeterministic counterexample based on a new choice of Reed--Solomon local codes, and then convert this example into a causal code using an edge orientation and local search.