MIXING MESSAGES BEATS ROUTING THEM, AFTER 22 YEARS OF DOUBT

Picture a network of cables in which several senders each want to reach their own receiver. The classic approach is routing: each message travels like a parcel along one or more paths, and traffic can even be split across many paths in any proportion. Network coding adds a further freedom: intermediate nodes may combine the messages they receive — for instance by adding them — instead of merely forwarding them.

The question is whether that freedom ever lets more data through. The paper focuses on undirected networks, where a cable can carry data in either direction but both directions share a single capacity.

A conjecture confirmed case after case

In 2004, Li and Li conjectured that in this setting coding brings no advantage over fractional routing; Harvey, Kleinberg and Rasala Lehman formulated the same conjecture independently. Over the next two decades it was confirmed for one class of networks after another — two sessions, certain planar networks, networks with at most six coding nodes, and more — but never settled in general. Other results in complexity theory, such as lower bounds for sorting integers in external memory and for multiplication circuits, had even been proved assuming it.

Known theory already limited the stakes: coding can beat routing by at most a logarithmic factor. And a 2017 result by Braverman, Garg and Schvartzman showed that a single network with a strict coding advantage could be amplified into a much larger gap. Everything came down to finding one finite example.

Adding is enough

The appendix gives the basic gadget, which shows why blending can help. Place several sources around a hub v, their receivers around another hub w, and join v and w by one cable. Each source also has small side paths to the other receivers. In three rounds, the middle cable carries the sum of all messages; each receiver gets that sum plus the other messages from the side paths, and recovers its own by subtraction. Without the middle cable, each source is five hops from its receiver.

That gadget, from earlier work by Haeupler, Wajc and Zuzic, makes coding faster, but not by itself able to carry more: a long path can still run a high-rate pipeline.

A circuit turned into a network

Xindan Zhang and Baochun Li, of the University of Toronto, and Zongpeng Li, of Tsinghua University, found the missing step. They turn a short code into a reversible computation — a circuit of invertible integer additions that computes, copies the result, then undoes its intermediate work. Then they build a new network whose physical cables are the wires of that circuit, and give every register of the computation, including scratch registers, its own sender–receiver demand.

A careful accounting of “time” along the wires does the rest. Summed over all wires, the lengths exactly match the minimum distances the demands must cover. But the designated demands cannot avoid certain gates that cost two extra units. So routing must fall strictly short of full rate, while the code uses each cable exactly once and, pipelined over many blocks, approaches a rate of one.

What is proved

• A finite connected network, with every node linked to at most three others and unit capacity on every cable, on which a simple binary linear code beats the best possible fractional routing. The 2004 conjecture is false.
• The same integer construction works over every finite field and every non-trivial finite abelian group at once.
• By repeatedly combining copies, the authors build infinite families of networks where coding approaches full rate while routing drops like a power of 1/log n — a polylogarithmic advantage.

The paper does not give the number of nodes in its counterexample. Its building block alone is a code that lasts 13,122 rounds.

Checked by machine

Both the finite counterexample and the family theorem are formalised in the Lean proof assistant. According to the authors, an audit of 2,472 declarations and 1,755 theorems shows that the proofs use only Lean’s three standard axioms, with no incomplete proofs; an independent re-check in a fresh environment also succeeded, though with the same Lean kernel.

What remains open

The authors list three questions: the true size of the advantage on their finite example, whether the known logarithmic ceiling is actually reached, and whether a small counterexample exists. Their last sentence sums up where things stand: “Coding, it turns out, does help in undirected networks; how much it can help remains to be seen.”

AI use declared. A footnote states that OpenAI’s GPT-6 Astra assisted in developing the proofs and the Lean code.