Hellinger volume and number-on-the-forehead communication complexity
From MaRDI portal
Publication:295642
DOI10.1016/j.jcss.2016.03.005zbMath1342.68131arXiv1407.5425MaRDI QIDQ295642
Troy Lee, Fengming Wang, Nikos Leonardos, Michael E. Saks
Publication date: 13 June 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.5425
94A15: Information theory (general)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- The BNS lower bound for multi-party protocols is nearly optimal
- On ACC
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- The Pattern Matrix Method
- Space lower bounds for distance approximation in the data stream model
- Two applications of information complexity
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- Rounds in Communication Complexity Revisited
- Quantum communication complexity of symmetric predicates
- Communication Complexity
- Multiparty Communication Complexity and Threshold Circuit Size of AC^0
- Communication Complexity and Quasi Randomness
- The multiparty communication complexity of set disjointness
- Lower Bounds for Quantum Communication Complexity
- Elements of Information Theory
- Communication lower bounds using directional derivatives
- Automata, Languages and Programming
- Automata, Languages and Programming
- Lower bounds in communication complexity based on factorization norms
- The BNS-Chung criterion for multi-party communication complexity
