Optimal collapsing protocol for multiparty pointer jumping

DOI10.1007/S00224-013-9476-XMaRDI QIDQ2441545zbMATH OpenOpenAlexFDO

Authors Hongyu Liang

Publication date 25 March 2014

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-013-9476-x

zbMATH Keywords

collapsing protocolmultiparty communication complexitynumber-on-the-forehead modelpointer jumpingtotal influence

Mathematics Subject Classification ID

Network protocols (68M12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication networks in operations research (90B18) (n)-person games, (n>2) (91A06) Other game-theoretic models (91A40)

Recommendations

• scientific article; zbMATH DE number 6146451
• One-way multiparty communication lower bound for pointer jumping with applications
• Some bounds on multiparty communication complexity of pointer jumping
• NOF-Multiparty Information Complexity Bounds for Pointer Jumping
• Some bounds on multiparty communication complexity of pointer jumping

Cites work

• A lower bound for finding predecessors in Yao's cell probe model
• Automata, Languages and Programming
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Communication Complexity
• scientific article; zbMATH DE number 3122238 (Why is no real title available?)
• scientific article; zbMATH DE number 5764792 (Why is no real title available?)
• scientific article; zbMATH DE number 5764809 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1016362 (Why is no real title available?)
• scientific article; zbMATH DE number 6146451 (Why is no real title available?)
• scientific article; zbMATH DE number 5485570 (Why is no real title available?)
• Lower bounds for one-way probabilistic communication complexity and their application to space complexity
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
• Lower bounds for union-split-find related problems on random access machines
• NOF-Multiparty Information Complexity Bounds for Pointer Jumping
• On ACC
• Rounds in Communication Complexity Revisited
• Some bounds on multiparty communication complexity of pointer jumping
• The cost of the missing bit: Communication complexity with help
• The space complexity of approximating the frequency moments

Cited in

(5)

• Some bounds on multiparty communication complexity of pointer jumping
• The function-inversion problem: barriers and opportunities
• scientific article; zbMATH DE number 6146451 (Why is no real title available?)
• NOF-Multiparty Information Complexity Bounds for Pointer Jumping
• Pointer chasing with unlimited interaction

This page was built for publication: Optimal collapsing protocol for multiparty pointer jumping

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