Undirected Network Coding and Faster External-Memory Integer Sorting
In the authors' words
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 integers of bits, a memory holding integers, and block transfers of integers, where , the number of block transfers is , where 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.
Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 38 pages