The Multiple Unicast Conjecture is False
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 𝔽9 on a 182-vertex bipartite subgraph of the point-line incidence graph of 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)ε) for some ε>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.
Related
BibTeX
@misc{braverman2026multiple,
title = {{The Multiple Unicast Conjecture is False}},
author = {Mark Braverman and Zhongtian He},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10108},
eprint = {2610.10108},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10108},
}
RIS
TY - UNPB
TI - The Multiple Unicast Conjecture is False
AU - Mark Braverman
AU - Zhongtian He
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10108
UR - https://arxiv.org/abs/2610.10108
AB - 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 𝔽_9 on a 182-vertex bipartite subgraph of the point-line incidence graph of 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)^ε) for some ε>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.
ER -