One-way multiparty communication lower bound for pointer jumping with applications
From MaRDI portal
Publication:532058
DOI10.1007/s00493-009-2667-zzbMath1224.68038MaRDI 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
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68R99: Discrete mathematics in relation to computer science
Related Items
Communication Lower Bounds Using Directional Derivatives, One-way multiparty communication lower bound for pointer jumping with applications, The function-inversion problem: barriers and opportunities, The Multiparty Communication Complexity of Set Disjointness
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
