Source-linked AI summary
The Multiple Unicast Conjecture is False
Mark Braverman, Zhongtian He
TL;DR
The paper addresses whether network coding can outperform fractional multicommodity flow in undirected multiple-unicast networks. It constructs a nondeterministic counterexample and converts it into a causal code. The resulting coding gap is Ω(log^ε n) for some ε > 0.
Problem
The undirected multiple-unicast conjecture asks whether network coding can offer a throughput advantage over fractional multicommodity flow.
Source: §1 · p. 2Method
The paper uses a nondeterministic coding construction to guide a counterexample, then converts it into a causal code using an edge orientation and local search.
Source: §1 · p. 3Results
The coding gap for undirected multiple unicast is Ω(log^ε n) for some constant ε > 0.
Source: §1 · p. 2Takeaways & Limitations
The construction refutes the conjecture that network coding offers no throughput advantage over multicommodity flow in undirected graphs.
Source: §1 · p. 2Nondeterministic certificate symbols may depend on the entire input and proposed-output vectors, so their rate comparison alone does not provide a chronological transmission protocol.
Source: §3 · p. 5
Abstract
from arXiv · showhide
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 $\Omega((\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.
1 Introduction
The paper refutes the conjecture that network coding offers no throughput advantage over fractional multicommodity flow in undirected multiple-unicast graphs. It presents a nondeterministic counterexample and a causal construction, yielding an asymptotically growing coding-gap family.
1 Introduction
- A positive resolution of the conjecture would have implied complexity-theoretic lower bounds, including an Ω(n log n) lower bound for constant-degree Boolean circuits computing integer multiplication.The stated consequences also include lower bounds for external-memory and oblivious computation.Source: §1 · p. 2
- Theorem 1.1 establishes a network-coding advantage for multiple unicast in an undirected graph.The paper thereby refutes the conjecture that coding offers no throughput advantage over fractional multicommodity flow.Source: §1 · p. 2
- The undirected multiple-unicast coding gap is Ω(log^ε n) for some constant ε > 0.The gap is the maximum ratio of network-coding throughput to multicommodity-flow throughput; amplifies an instance with an advantage into a growing family.Source: §1 · p. 2
- The construction first refutes a nondeterministic version of the conjecture, where vertices locally check edge bits, then converts the example into a causal code.It uses a high-girth graph and error-correcting-code architecture from, new Reed–Solomon codes, and an edge orientation with local search.Source: §1 · p. 3
- The paper presents the nondeterministic construction before the causal code because it is easier to parse and avoids the orientation and local-search steps.The authors also describe the nondeterministic constructions as somewhat canonical and potentially independently interesting, in connection with distributed certification.Source: §1 · p. 3
2 Preliminaries
The preliminaries define the multiple-unicast instance and the requirements for network-coding solutions. They also describe throughput in terms of message entropy and edge-capacity constraints.
2 Preliminaries
- A multiple-source unicast instance consists of an undirected capacitated graph and sessions, each specified by a source, sink, and communication demand.Messages from the sources are sampled independently from their respective distributions.Source: §2 · pp. 3–4
- The authors report that direct attempts to prove the weaker conjecture with GPT did not make appreciable progress, motivating nondeterministic versions as intermediate points.They note that those attempts had access to earlier unicast works.Source: §2 · p. 3
- A network-coding solution assigns an alphabet and encoding function to each edge and must satisfy correctness and causality.Correctness requires each sink to recover its corresponding source’s message; causality requires edge transmissions to be computable from received symbols.Source: §2 · p. 4
- The throughput of a coding solution is the largest rate satisfying the message-entropy and edge-capacity constraints, and instance throughput is the supremum over valid solutions and source distributions.For each edge, the two directional transmission entropies together are bounded by its capacity at the chosen scale.Source: §2 · p. 4
3 A Nondeterministic Code on PG(2,9)
A nondeterministic code on a subgraph of the PG(2,9) incidence graph separates certificate-based network coding from fractional multicommodity flow. Local polynomial constraints provide certificates for arbitrary inputs and force every accepting execution to decode correctly.
3 A Nondeterministic Code on PG(2,9)
- The construction uses a 182-vertex, 744-edge graph supporting 166 independent unicast messages over F9, formed by deleting 166 edges from the PG(2,9) incidence graph.Each deleted edge defines a source–sink pair, and the deleted edges form an information set.Source: §3 · pp. 5, 7
- The certificate-to-flow throughput ratio is at least 415/372: one certificate symbol per physical edge supports one symbol per session, while flow rate r requires at least 830r total edge load against 744 capacity.The flow bound is Rflow ≤ 744/830 = 372/415.Source: §3 · p. 5
- The rate comparison concerns nondeterministic verification, not a chronological protocol, because certificate symbols may depend on the full input and proposed-output vectors.The construction therefore establishes a certificate-based separation rather than, by itself, a causal transmission scheme.Source: §3 · p. 5
- At either vertex type, five distinct incident evaluations uniquely determine the five coefficients a0,...,a4, since a nonzero homogeneous quartic cannot vanish at five distinct projective points and cubing permutes the projective line over F9.Source: §3 · p. 6
- A certificate gives one field element per physical edge and proposed outputs at destinations; local checks admit an execution for every input and ensure every accepting execution decodes correctly.The proof uses assignments in W to establish existence and test assignments for each deleted edge to establish correctness.Source: §3 · pp. 7, 9
- Every source–sink pair is connected but has distance at least five, so routing one symbol per session requires at least 830 field-symbol transmissions.The distance bound follows from bipartiteness, deletion of the source–sink edge, and the absence of four-cycles.Source: §3 · pp. 5, 9
4 The Deterministic Certificate
The section specifies a deterministic causal code on an undirected graph and shows that it outperforms fractional multicommodity flow. Its flow bound follows from the 157 sessions requiring at least five edge transmissions each, against 735 units of total edge capacity.
4 The Deterministic Certificate
- The construction supports 157 independent unicast messages on a 182-vertex, 735-edge undirected graph over F9, using one symbol per physical edge per execution.The code is deterministic and causal, with a fixed vertex-processing order.Source: §4 · pp. 10, 12
- 785r total edge load is required for common routing rate r, so 735 unit-capacity edges imply r ≤ 147/157.Each of the 157 sessions needs at least five edge transmissions along any route.Source: §4 · p. 10
- The graph is formed from the point-line incidence graph of PG(2,9) by deleting 175 edges, with source-destination pairs assigned to selected edges.The processing order orients physical edges earlier-to-later and deleted edges later-to-earlier.Source: §4 · pp. 10–11
- Each vertex interpolates from five values already available to it, then sends evaluations on outgoing physical edges and decodes demands at their destinations.C-edge values are fixed to zero; source symbols enter on B-edges.Source: §4 · pp. 11–12
- The resulting deterministic causal linear code strictly outperforms routing in this undirected multiple-unicast instance.Each demand joins endpoints of a deleted edge, and the code’s causal interpolation computes the compatible assignment.Source: §4 · pp. 10, 12
A Missing definitions
The appendix specifies the deleted-edge set and the vertex-processing order used in the construction.
A Missing definitions
- The set R consists of 175 deleted edge indices.Source: A Missing definitions · p. 14
- The processing order π is given as one ordered list indexed from π0 through π181.Source: A Missing definitions · p. 15
- The stated reading order for π is left to right, then top to bottom.Source: A Missing definitions · p. 15
B An elementary proof of the dimension bound
The appendix proves a lower bound on the dimension of the space of assignments satisfying the local rules. It constructs 166 independent assignments using bidegree-(4,4) polynomials and proves their independence through polynomial identities and distinct leading terms.
B An elementary proof of the dimension bound
- The proof builds assignments from bidegree-(4,4) polynomials, retaining monomials that are divisible by neither of two specified expressions.The counting argument yields 166 retained monomials.Source: B An elementary proof of the dimension… · pp. 16–17
- These polynomial assignments satisfy the local rules because fixing either endpoint gives a homogeneous quartic in the other endpoint’s local coordinates.At line vertices, characteristic three makes the transformed expression a homogeneous quartic.Source: B An elementary proof of the dimension… · p. 16
- A vanishing assignment forces the quartic restriction to vanish identically on each relevant projective line, yielding polynomial identities used to prove independence.The proof uses the fact that a nonzero binary quartic has at most four distinct projective zeros.Source: B An elementary proof of the dimension… · pp. 17–18
- The retained monomials yield distinct leading terms after substitution, so their substituted polynomials are linearly independent.The degree comparison also forces the auxiliary polynomial to vanish.Source: B An elementary proof of the dimension… · pp. 18–19
- 166 selected edge assignments belong to W and are linearly independent, establishing dim(W) ≥ 166.W is the space of assignments to candidate edges satisfying the local conditions simultaneously.Source: B An elementary proof of the dimension… · pp. 16, 19