The communication complexity of pointer chasing: applications of entropy and sampling

DOI10.1145/301250.301413MaRDI QIDQ6483601zbMATH OpenFDO

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

Publication date 29 September 2016

Published in 1345.68133 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/301250.301413

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17)

Recommendations

• The communication complexity of pointer chasing
• Some bounds on multiparty communication complexity of pointer jumping
• Some bounds on multiparty communication complexity of pointer jumping
• scientific article; zbMATH DE number 1954386
• Probabilistic communication complexity
• Randomized communication complexity of approximating Kolmogorov complexity
• Probabilistic communication complexity over the reals
• scientific article; zbMATH DE number 4197419
• The Probabilistic Communication Complexity of Set Intersection
• Bounds on tradeoffs between randomness and communication complexity

Cited in

(6)

• scientific article; zbMATH DE number 1954386 (Why is no real title available?)
• Some bounds on multiparty communication complexity of pointer jumping
• Pointer chasing via triangular discrimination
• The communication complexity of pointer chasing
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• Pointer chasing with unlimited interaction

This page was built for publication: The communication complexity of pointer chasing: applications of entropy and sampling

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