The Hardness of Median in the Synchronized Bit Communication Model

DOI10.1007/978-3-642-20877-5_40zbMath1331.68080arXiv1102.1208OpenAlexW2138093554MaRDI QIDQ3010421

Karolina Sołtys

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.1208

zbMATH Keywords

mediancommunication complexityround complexitysynchronized bit model

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Selection and sorting with limited storage
• Rounds in Communication Complexity Revisited
• Communication Complexity
• The communication complexity of pointer chasing

This page was built for publication: The Hardness of Median in the Synchronized Bit Communication Model