Lower bounds for external memory integer sorting via network coding
From MaRDI portal
Publication:5212840
DOI10.1145/3313276.3316337zbMath1433.68110arXiv1811.01313OpenAlexW2964250714MaRDI QIDQ5212840
Kasper Green Larsen, Alireza Farhadi, Elaine Shi, Mohammad Taghi Hajiaghayi
Publication date: 30 January 2020
Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.01313
Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
A logarithmic lower bound for oblivious RAM (for all Parameters) ⋮ Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ A theory of composition for differential obliviousness ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Lower Bounds for Multiplication via Network Coding ⋮ OptORAMa: optimal oblivious RAM
This page was built for publication: Lower bounds for external memory integer sorting via network coding
