An Optimal Lower Bound for Distinct Elements in the Message Passing Model

DOI10.1137/1.9781611973402.54zbMath1422.68096OpenAlexW4239751253MaRDI QIDQ5384015

David P. Woodruff, Qin Zhang

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

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)

Related Items (6)

The Range of Topological Effects on Communication ⋮ When distributed computation is communication expensive ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Unnamed Item ⋮ Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy ⋮ The Communication Complexity of Distributed epsilon-Approximations

This page was built for publication: An Optimal Lower Bound for Distinct Elements in the Message Passing Model