Hellinger volume and number-on-the-forehead communication complexity
From MaRDI portal
(Redirected from Publication:295642)
Abstract: Information-theoretic methods have proven to be a very powerful tool in communication complexity, in particular giving an elegant proof of the linear lower bound for the two-party disjointness function, and tight lower bounds on disjointness in the multi-party number-in-the-hand (NIH) model. In this paper, we study the applicability of information theoretic methods to the multi-party number-on-the-forehead model (NOF), where determining the complexity of disjointness remains an important open problem. There are two basic parts to the NIH disjointness lower bound: a direct sum theorem and a lower bound on the one-bit AND function using a beautiful connection between Hellinger distance and protocols revealed by Bar-Yossef, Jayram, Kumar and Sivakumar [BYJKS04]. Inspired by this connection, we introduce the notion of Hellinger volume. We show that it lower bounds the information cost of multi-party NOF protocols and provide a small toolbox that allows one to manipulate several Hellinger volume terms and lower bound a Hellinger volume when the distributions involved satisfy certain conditions. In doing so, we prove a new upper bound on the difference between the arithmetic mean and the geometric mean in terms of relative entropy. We then apply these new tools to obtain a lower bound on the informational complexity of the AND_k function in the NOF setting. Finally, we discuss the difficulties of proving a direct sum theorem for information cost in the NOF model.
Recommendations
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
- An information statistics approach to data stream and communication complexity
- Inner product and set disjointness: beyond logarithmically many parties
- Simplified lower bounds on the multiparty communication complexity of disjointness
Cites work
- scientific article; zbMATH DE number 524134 (Why is no real title available?)
- scientific article; zbMATH DE number 2005717 (Why is no real title available?)
- An information statistics approach to data stream and communication complexity
- Automata, Languages and Programming
- Automata, Languages and Programming
- Communication Complexity
- Communication Complexity and Quasi Randomness
- Communication lower bounds using directional derivatives
- Disjointness is hard in the multiparty number-on-the-forehead model
- Elements of Information Theory
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- Lower Bounds for Quantum Communication Complexity
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Lower bounds in communication complexity based on factorization norms
- Multiparty Communication Complexity and Threshold Circuit Size of AC^0
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- On ACC
- On the power of small-depth threshold circuits
- Quantum communication complexity of symmetric predicates
- Rounds in Communication Complexity Revisited
- Space lower bounds for distance approximation in the data stream model
- The BNS lower bound for multi-party protocols is nearly optimal
- The BNS-Chung criterion for multi-party communication complexity
- The multiparty communication complexity of set disjointness
- The pattern matrix method
- Two applications of information complexity
This page was built for publication: Hellinger volume and number-on-the-forehead communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q295642)
