Lower Bounds for External Memory Integer Sorting via Network Coding

DOI10.1137/20M1321887zbMath1475.94052OpenAlexW3202340437MaRDI QIDQ5157396

Elaine Shi, Alireza Farhadi, Kasper Green Larsen, Mohammad Taghi Hajiaghayi

Publication date: 18 October 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1321887

zbMATH Keywords

network codingexternal memoryinteger sortingLi and Li conjecture

Mathematics Subject Classification ID

Searching and sorting (68P10) Information storage and retrieval of data (68P20) Coding theorems (Shannon theory) (94A24)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model
• How to compress interactive communication
• Deterministic sorting in O ( n log log n ) time and linear space
• Should Tables Be Sorted?
• Network information flow
• Network coding in undirected graphs is either very helpful or not helpful at all
• DecreaseKeys are expensive for external memory priority queues
• A Faster External Memory Priority Queue with DecreaseKeys
• A Reduction Approach to the Multiple-Unicast Conjecture in Network Coding
• On the capacity of information networks
• On the capacity of information networks

This page was built for publication: Lower Bounds for External Memory Integer Sorting via Network Coding