arXiv preprint ·
The Multiple Unicast Conjecture is False
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
An ETH-based quasipolynomial lower bound for Dualization
Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection
Fast Almost-Uniform Sampling of Random $k$-SAT Solutions
Polynomial directed treewidth forces a large bramble with congestion two
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.