Lower bounds on communication complexity

DOI10.1016/0890-5401(87)90037-XzbMath0635.68034OpenAlexW2008078482MaRDI QIDQ1097691

Pavol Ďuriš, Georg Schnitger, Zvi Galil

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90037-x

zbMATH Keywords

protocolcommunication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (15)

Communication Complexity and Lower Bounds on Multilective Computations ⋮ Tight lower bounds for query processing on streaming and external memory data ⋮ On problem transformability in VLSI ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ Superlinear lower bounds for multipass graph processing ⋮ Multiparty communication complexity and very hard functions ⋮ Lower bounds for one-way probabilistic communication complexity ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ New lower bounds and hierarchy results for restricted branching programs ⋮ The communication complexity of pointer chasing ⋮ Lower bounds on the multiparty communication complexity ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Pointer chasing via triangular discrimination ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Communication complexity and combinatorial lattice theory

Cites Work

• Information Transfer in Distributed Computing with Applications to VLSI
• Information Transfer under Different Sets of Protocols

This page was built for publication: Lower bounds on communication complexity