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

communication complexitylower boundpointer chasing problemupper bound

Mathematics Subject Classification ID

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

Review text

The bounded round two-party communication complexity of a particular problem -- the pointer chasing problem -- is studied. First, a nonlinear lower bound is proved that matches the known upper bound for this problem. Then, the bit version of the problem is considered, and upper and lower bounds are shown. Also, a certain generalization of the pointer chasing problem, the so-called \(s\)-pointer game, is considered and its upper bound obtained.

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

• Communication complexity
• Different Modes of Communication
• 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?)
• 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

(8)

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

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)