In the 10/2020 edition of the magazine Communications of the ACM, associate professor Kasper Green Larsens’ paper Lower Bounds for External Memory Integer Sorting via Network Coding is featured as a research highlight.

2020.09.29 |

In the paper, the authors present a tight conditional lower bound on the complexity of external memory sorting of integers. Their lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs.

Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main memory; thus, external memory sorting algorithms, first introduced by Aggarwal and Vitter, are often used. The complexity of comparison-based external memory sorting has been understood for decades by now; however, the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of *n* integer keys of Θ(lg *n*) bits each in *O*(*n*) time using the classic Radix Sort algorithm; however, in external memory, there are no faster integer sorting algorithms known than the simple comparison-based ones. Whether such algorithms exist has remained a central open problem in external memory algorithms for more than three decades.

Read the full article from 10/2020 Communications of the ACM (vol. 63, no.10), here: https://cacm.acm.org/magazines/2020/10/247602-lower-bounds-for-external-memory-integer-sorting-via-network-coding/fulltext