One-way multiparty communication lower bound for pointer jumping with applications
From MaRDI portal
Publication:532058
DOI10.1007/s00493-009-2667-zzbMath1224.68038OpenAlexW2076448565MaRDI QIDQ532058
Publication date: 26 April 2011
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-009-2667-z
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Discrete mathematics in relation to computer science (68R99)
Related Items (4)
The function-inversion problem: barriers and opportunities ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Communication Lower Bounds Using Directional Derivatives
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- One-way multiparty communication lower bound for pointer jumping with applications
- An information statistics approach to data stream and communication complexity
- Disjointness is hard in the multiparty number-on-the-forehead model
- On the power of small-depth threshold circuits
- The cost of the missing bit: Communication complexity with help
- Communication complexity
- Lower bounds on communication complexity
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Some bounds on multiparty communication complexity of pointer jumping
- Improved depth lower bounds for small distance connectivity
- The space complexity of approximating the frequency moments
- On ACC
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
- The NOF Multiparty Communication Complexity of Composed Functions
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- Rounds in Communication Complexity Revisited
- Communication Complexity of Simultaneous Messages
- Communication Complexity
- Multiparty Communication Complexity and Threshold Circuit Size of AC^0
- Communication Complexity and Quasi Randomness
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
- NOF-Multiparty Information Complexity Bounds for Pointer Jumping
- Improved Separations between Nondeterministic and Randomized Multiparty Communication
- The BNS-Chung criterion for multi-party communication complexity
This page was built for publication: One-way multiparty communication lower bound for pointer jumping with applications
