The communication complexity of pointer chasing

DOI10.1006/JCSS.2000.1731MaRDI QIDQ5943092zbMATH OpenOpenAlexFDO

Authors Stephen J. Ponzio, S. Venkartesh, Jaikumar Radhakrishnan

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

lower boundupper boundcommunication complexitypointer chasing problem

Mathematics Subject Classification ID

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

Recommendations

• The communication complexity of pointer chasing: applications of entropy and sampling
• Pointer chasing via triangular discrimination
• scientific article; zbMATH DE number 1954386
• NOF-Multiparty Information Complexity Bounds for Pointer Jumping
• scientific article; zbMATH DE number 6146451

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1335889 (Why is no real title available?)
• Communication complexity
• Different Modes of Communication
• Lower bounds on communication complexity
• Randomness is linear in space
• Rounds in Communication Complexity Revisited
• Some bounds on multiparty communication complexity of pointer jumping

Cited in

(7)

• Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
• The hardness of median in the synchronized bit communication model
• scientific article; zbMATH DE number 1954386 (Why is no real title available?)
• A direct product theorem for two-party bounded-round public-coin communication complexity
• Superlinear lower bounds for multipass graph processing
• The communication complexity of pointer chasing: applications of entropy and sampling
• Pointer chasing via triangular discrimination

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5943092)