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
TL;DR
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.
Abstract
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.
Problem
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.
Approach
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.
Results
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 size | Classical comparison sorting | This 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