Skip to content
Preprint

Undirected Multiple-Unicast Network Coding and Faster External-Memory Integer Sorting

Oct 2026 · 1 citation · 34 references
Computer Science Mathematics

TL;DR

Under the external-memory model specified in this paper, the deterministic sorting algorithm formally verified the algorithm's correctness and I/O complexity bound in Lean~4.0 is formally verified.

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 $\Theta(\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=1.5\times10^{-5}$ is an absolute constant. This bound asymptotically improves on the classical $\Theta\!\left(\frac{N}{B}\left[1+ \frac{\log(N/M)}{\log(M/B)}\right]\right)$ 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.

View source

Similar papers

Preprint Oct 2026

Network Coding Can Beat Routing in Undirected Multiple-Unicast Networks

Network coding lets the nodes of a network combine messages rather than merely forward them. In undirected networks, where the two directions of an edge share its capacity, Li and Li conjectured in 2004 that coding offers no advantage over fractional routing; the conjecture has been confirmed for many special classes b...

Xin-Dan Zhang, Bao-Chun Li, Zong-Peng Li · 5 citations
Preprint Oct 2026

When Multiple-Unicast Feasibility Is Equivalent to Single-Sink Routability

In communication networks, network coding allows intermediate nodes to combine messages, achieving transmission rates unattainable by routing alone in many multicast settings. In multiple unicast, where each source sends a message only to its prescribed destination, a central question is under what conditions fractiona...

Si-Rui Liu, Zong-Peng Li, Bao-Chun Li · 0 citations
Preprint Oct 2026

The Multiple Unicast Conjecture is False

The undirected multiple-unicast conjecture [LL04] asserts that network coding offers no throughput advantage over multicommodity flow. We refute this conjecture by constructing a deterministic linear network code over $\mathbb{F}_9$ on a 182-vertex bipartite subgraph of the point-line incidence graph of $\mathrm{PG}(2,...

Mark Braverman, Zhong-Tian He · 5 citations
Preprint Oct 2026

Constant-Factor Approximation for Non-Splitting Coflow Scheduling in Heterogeneous Parallel Networks via Iterative Relaxation

Coflows capture the collective communication requirements of data-parallel applications, and scheduling them well is essential to the performance of modern data centers. We study non-splitting coflow scheduling in a heterogeneous parallel network whose $m$ network cores may be Electronic Packet Switches (EPS), not-all-...

Chi-Yeh Chen · 0 citations
Sep 2026

Concurrent Coded Signal-Multiplexing Ranging for Half-Duplex Asynchronous Networks

A concurrent coded SM-NR (CC-SM-NR) framework for asynchronous half-duplex networks is proposed and a low-complexity scheduling algorithm is proposed that achieves the minimum round count within the constant-weight codeword class.

Zi-Jian Zhang, Yuan Shen · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.