Undirected Network Coding and Faster External-Memory Integer Sorting
Abstract
In undirected multiple-unicast networks, where independent messages are sent between specified source--destination pairs, network coding allows intermediate nodes to combine messages, whereas fractional routing splits and forwards individual messages along paths without mixing them. Proposed in 2004 by Li and Li and independently by Harvey, Kleinberg, and Lehman, the multiple-unicast conjecture---a central conjecture in network coding with deep connections to computational complexity---asserts that network coding and fractional routing have the same achievable rate region. We construct a counterexample refuting this conjecture and use it to reduce block transfers in external-memory data rearrangement, thereby accelerating external-memory integer sorting and answering in the affirmative the longstanding question of Aggarwal and Vitter (1988) on whether integer operations can beat the comparison-sorting input/output (I/O) bound. Specifically, 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≤ M≤ N, the number of block transfers is O (N/B[1+ (log N)/((log(M/B))1−ε(log M)ε) ]), where ε=1.5×10−5 is an absolute constant. This bound asymptotically improves on the classical Θ (N/B[1+ log(N/M)/log(M/B)]) comparison-sorting bound in certain parameter regimes. Under the external-memory model specified in this paper, we have formally verified the algorithm's correctness and I/O complexity bound in Lean~4.
Related
- Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks
- Integrating multi-source local information for global undirected graph reconstruction via integer programming
- Communication Advantages from Quantum Dense Network Coding
- Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs
- Undirected edge geography games on stacked prism graphs
BibTeX
@misc{li2026undirected,
title = {{Undirected Network Coding and Faster External-Memory Integer Sorting}},
author = {Baochun Li and Zongpeng Li and Sirui Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20079},
eprint = {2610.20079},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20079},
}
RIS
TY - UNPB
TI - Undirected Network Coding and Faster External-Memory Integer Sorting
AU - Baochun Li
AU - Zongpeng Li
AU - Sirui Liu
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.20079
UR - https://arxiv.org/abs/2610.20079
AB - In undirected multiple-unicast networks, where independent messages are sent between specified source--destination pairs, network coding allows intermediate nodes to combine messages, whereas fractional routing splits and forwards individual messages along paths without mixing them. Proposed in 2004 by Li and Li and independently by Harvey, Kleinberg, and Lehman, the multiple-unicast conjecture---a central conjecture in network coding with deep connections to computational complexity---asserts that network coding and fractional routing have the same achievable rate region. We construct a counterexample refuting this conjecture and use it to reduce block transfers in external-memory data rearrangement, thereby accelerating external-memory integer sorting and answering in the affirmative the longstanding question of Aggarwal and Vitter (1988) on whether integer operations can beat the comparison-sorting input/output (I/O) bound. Specifically, 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≤ M≤ N, the number of block transfers is O (N/B[1+ (log N)/((log(M/B))^1−ε(log M)^ε) ]), where ε=1.5×10^−5 is an absolute constant. This bound asymptotically improves on the classical Θ (N/B[1+ log(N/M)/log(M/B)]) comparison-sorting bound in certain parameter regimes. Under the external-memory model specified in this paper, we have formally verified the algorithm's correctness and I/O complexity bound in Lean~4.
ER -