Network coding can beat standard routing in undirected networks
A constructed network supported 157 sessions at a coding rate of at least 1, while standard routing reached at most 147/157.
Edited by Boris Djordjevic · Paperfoot
In a preprint, a theory paper refuted the undirected multiple-unicast conjecture by constructing a deterministic linear network code on a 182-vertex graph. The conjecture asserted that network coding offers no throughput advantage over multicommodity flow in undirected networks. Network coding allows routers to combine data packets, whereas multicommodity flow routes data streams without combining them. The authors' code supported 157 independent unicast sessions at a common coding rate of at least 1, while every fractional multicommodity flow achieved at most 147/157.
To guide the construction, the authors introduced a nondeterministic network coding model based on locally verifiable certificates. They used GPT-6 to find a counterexample based on Reed–Solomon local codes, then converted it into a causal code using edge orientation and local search. By an existing amplification theorem, this construction yields a family of undirected instances where network coding maintains an advantage.
Why it matters
The mathematical proof settles an open conjecture in theoretical computer science, showing that network coding can achieve higher data throughput than standard routing in undirected networks. It proves that combining information at network nodes offers a throughput advantage across an entire family of network instances.
Caveats
The result is a theoretical proof on a specialized mathematical graph rather than an evaluation on physical communications networks. Additionally, the paper is a preprint that has not yet undergone peer review.
In this paper
multiple unicast
- Methods
- deterministic linear network code (this paper)nondeterministic model of network coding (this paper)fractional multicommodity flow (baseline)GPT-6ChatGPT
Results
- deterministic linear network code, common coding rate, on a 182-vertex bipartite subgraph of the point-line incidence graph of PG(2,9): at least 1
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.
Abstract
What it shows
- A deterministic linear network code on a 182-vertex bipartite subgraph of the point-line incidence graph of PG(2,9) refutes the undirected multiple-unicast conjecture.
We refute this conjecture by constructing a deterministic linear network code over F9 on a 182-vertex bipartite subgraph of the point-line incidence graph of PG(2,9).
Abstract
- There exists a network coding advantage for multiple unicast in an undirected graph.
There exists a network coding advantage for multiple unicast in an undirected graph.
1.1.
- The network coding gap for multiple unicast in an undirected graph is Ω((log n)^ε) for some constant ε>0.
The network coding gap for multiple unicast in an undirected graph is \Omega(\log^{\epsilon}n) for some constant \epsilon>0.
1.2.
- Any transmission scheme is also a nondeterministic scheme, but not vice versa.
Note that any transmission scheme is also a non-deterministic scheme, but not vise versa.
Non-deterministic version
Quoted word for word from the full text on arXiv.
The paper
The Multiple Unicast Conjecture is False
arXiv, Oct 7, 2026, Open access, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.10108
arXiv:2610.10108v1 in cs.IT, also cs.CC, cs.DM, cs.DS, math.IT
Cite as BibTeX
@misc{braverman2026multiple,
title = {The Multiple Unicast Conjecture is False},
author = {Braverman, Mark and He, Zhongtian},
year = {2026},
eprint = {2610.10108},
archivePrefix = {arXiv},
primaryClass = {cs.IT},
doi = {10.48550/arxiv.2610.10108},
url = {https://arxiv.org/abs/2610.10108}
}
