The communication complexity of pointer chasing

DOI10.1006/jcss.2000.1731zbMath0989.94004OpenAlexW2037817744MaRDI QIDQ5943092

Stephen J. Ponzio, S. Venkartesh

Publication date: 10 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2000.1731

zbMATH Keywords

upper boundlower boundcommunication complexitypointer chasing problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication theory (94A05)

Related Items (5)

Superlinear lower bounds for multipass graph processing ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ The Hardness of Median in the Synchronized Bit Communication Model ⋮ Pointer chasing via triangular discrimination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Communication complexity
• Lower bounds on communication complexity
• Some bounds on multiparty communication complexity of pointer jumping
• Randomness is linear in space
• Different Modes of Communication
• Rounds in Communication Complexity Revisited

This page was built for publication: The communication complexity of pointer chasing