Optimal collapsing protocol for multiparty pointer jumping
From MaRDI portal
Publication:2441545
DOI10.1007/s00224-013-9476-xzbMath1290.68048MaRDI QIDQ2441545
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
total influence; pointer jumping; multiparty communication complexity; collapsing protocol; number-on-the-forehead model
90B18: Communication networks in operations research
91A06: (n)-person games, (n>2)
91A40: Other game-theoretic models
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68M12: Network protocols
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The cost of the missing bit: Communication complexity with help
- A lower bound for finding predecessors in Yao's cell probe model
- Some bounds on multiparty communication complexity of pointer jumping
- The space complexity of approximating the frequency moments
- On ACC
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Lower bounds for union-split-find related problems on random access machines
- Rounds in Communication Complexity Revisited
- Boolean Circuits, Tensor Ranks, and Communication Complexity
- Communication Complexity
- Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
- Automata, Languages and Programming
- NOF-Multiparty Information Complexity Bounds for Pointer Jumping
