pipette
ENEnglish

Undirected Network Coding and Faster External-Memory Integer Sorting

Baochun Li, Zongpeng Li, Sirui Liu

PreprintDice ser un gran avance

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 38 pages