Lower bounds for external memory integer sorting via network coding
From MaRDI portal
Publication:5157396
DOI10.1137/20M1321887zbMATH Open1475.94052OpenAlexW3202340437MaRDI QIDQ5157396FDOQ5157396
Authors: Alireza Farhadi, Kasper Green Larsen, Elaine Shi, Mohammad T. 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
Recommendations
Information storage and retrieval of data (68P20) Coding theorems (Shannon theory) (94A24) Searching and sorting (68P10)
Cites Work
- Network information flow
- Deterministic sorting in O ( n log log n ) time and linear space
- Should Tables Be Sorted?
- How to compress interactive communication
- On the capacity of information networks
- On the capacity of information networks
- A faster external memory priority queue with DecreaseKeys
- The limits of buffering: a tight lower bound for dynamic membership in the external memory model
- On the capacity of multiple unicast sessions in undirected graphs
- A Reduction Approach to the Multiple-Unicast Conjecture in Network Coding
- Network coding in undirected graphs is either very helpful or not helpful at all
- DecreaseKeys are expensive for external memory priority queues
- Using hashing to solve the dictionary problem
- On the cell probe complexity of dynamic membership
Cited In (1)
This page was built for publication: Lower bounds for external memory integer sorting via network coding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5157396)
