Lower bounds for external memory integer sorting via network coding

DOI10.1137/20M1321887MaRDI QIDQ5157396zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

network codingexternal memoryinteger sortingLi and Li conjecture

Mathematics Subject Classification ID

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

Recommendations

• Lower bounds for external memory integer sorting via network coding
• scientific article; zbMATH DE number 4020488
• Lower bounds for external algebraic decision trees

Cites work

• A Reduction Approach to the Multiple-Unicast Conjecture in Network Coding
• A faster external memory priority queue with DecreaseKeys
• DecreaseKeys are expensive for external memory priority queues
• Deterministic sorting in O ( n log log n ) time and linear space
• How to compress interactive communication
• Network coding in undirected graphs is either very helpful or not helpful at all
• Network information flow
• On the capacity of information networks
• On the capacity of information networks
• On the capacity of multiple unicast sessions in undirected graphs
• On the cell probe complexity of dynamic membership
• Should Tables Be Sorted?
• The limits of buffering: a tight lower bound for dynamic membership in the external memory model
• Using hashing to solve the dictionary problem

Cited in

(1)

• Lower bounds for external memory integer sorting via network coding

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)