← All papers
First page of Undirected Network Coding and Faster External-Memory Integer Sorting

Undirected Network Coding and Faster External-Memory Integer Sorting

Baochun Li, Zongpeng Li, Sirui Liu

cs.DS Oct 14, 2026 · v1 cs.CC cs.IT
Formalizes the external-memory sorting theorem (correctness and I/O bounds) and the network-coding counterexample in Lean 4 with Mathlib, with a public repository.
Network coding allows intermediate nodes to combine messages, whereas routing only forwards them. The Li-Li conjecture asserts that network coding and fractional routing have the same capacity region in undirected multiple-unicast networks. We give a counterexample to this conjecture and apply it to external-memory integer sorting. Since Aggarwal and Vitter posed the question in 1988, whether integer sorting can beat the external-memory comparison bound has remained a central and extensively studied open problem. We give a deterministic sorting algorithm: for $N$ integers of $Θ(\log N)$ bits, a memory holding $M$ integers, and block transfers of $B$ integers, where $2B\le M\le N$, the number of block transfers is $O\left(\frac{N}{B}\left[1+\frac{\log N}{(\log(M/B))^{1-\varepsilon}(\log M)^\varepsilon}\right]\right)$, where $\varepsilon>0$ is an absolute constant. In a range of parameter regimes, this bound is asymptotically smaller than the classical comparison-sorting bound. We also use Lean 4 to verify the sorting algorithm's correctness and complexity bounds, and the strict advantage of coding over routing.

The Li–Li conjecture states that network coding cannot beat fractional routing in undirected multiple-unicast networks. If true, it would imply that external-memory integer sorting cannot beat the comparison bound, a question open since Aggarwal and Vitter in 1988.

The authors build a finite binary linear XOR circuit whose network has a coding rate strictly above every routing rate, which gives a counterexample. They reuse the circuit recursively to speed up address-field interchange permutations. Combining this with Columnsort and most-significant-digit radix sorting yields a deterministic external-memory integer sorting algorithm. Theorems 2.1 and 2.2 are formalized in Lean 4 with Mathlib, with ChatGPT/Codex assisting in writing the proofs.

The algorithm sorts N integers of Θ(log N) bits in O((N/B)[1 + log N / ((log(M/B))^{1-ε}(log M)^ε)]) block transfers, with ε = 1.8×10^-11. This beats the comparison-sorting bound in some parameter regimes. The routing rate is strictly below the coding rate of 1, and the main results are machine-checked in Lean.

Input sizeClassical comparison sortingThis work
N=B^2Θ(B log B)O(B (log B)^{1-ε})
N=B^3Θ(B^2 log B)O(B^2 (log B)^{1-ε})
I/O cost comparison for M=2B