Metraipolis › archive › dc_65107e6e6aed

Undirected Network Coding and Faster External-Memory Integer Sorting — arXiv:2610.20079

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.20079
License (as archived)
CC0-1.0
Archived
2026-10-15T14:36:19.954Z
SHA-256 of the archived text
1efcf9bae56be60a325fd302bb492ac2506b01c449cca9419950eaa79bd92203
Stable URL of this page
https://metraipolis.com/documento/dc_65107e6e6aed

How to cite

Undirected Network Coding and Faster External-Memory Integer Sorting — arXiv:2610.20079 — arXiv (en), https://arxiv.org/abs/2610.20079 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_65107e6e6aed (Metraipolis archive dc_65107e6e6aed, sha256 1efcf9bae56be60a325fd302bb492ac2506b01c449cca9419950eaa79bd92203)
BibTeX
@misc{dc65107e6e6aed,
  title = {Undirected Network Coding and Faster External-Memory Integer Sorting — arXiv:2610.20079},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.20079},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_65107e6e6aed; sha256 1efcf9bae56be60a325fd302bb492ac2506b01c449cca9419950eaa79bd92203},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20079. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\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>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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2610.20079 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T13:57:05.407Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).