arXiv preprint ·
Undirected Network Coding and Faster External-Memory Integer Sorting
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Network coding allows intermediate nodes to combine messages. Fractional routing instead splits each message among source-destination paths and forwards its parts without combining different messages. For undirected networks carrying independent messages between multiple source-destination pairs, the multiple-unicast conjecture asserts that the two methods achieve the same combinations of message rates. We give a finite counterexample and use its linear structure to accelerate external-memory integer sorting, addressing the question of whether integer operations can beat the comparison-sorting input/output (I/O) bound posed by Aggarwal and Vitter in 1988. 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\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. In some parameter ranges, this bound is asymptotically smaller than the classical comparison-sorting bound. Under the external-memory model specified in this paper, we have formally verified the algorithm's correctness and I/O complexity bound in Lean.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space
Parallel Repetition for Entangled Games via Conditional Relative Entropy
Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter
On the Complexity of Linear Programs with Parametric Constraint Matrices
Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.