Hellinger volume and number-on-the-forehead communication complexity

DOI10.1016/J.JCSS.2016.03.005zbMATH Open1342.68131arXiv1407.5425OpenAlexW2105673830MaRDI QIDQ295642FDOQ295642

Authors: Troy Lee, Nikos Leonardos, Fengming Wang, Michael Saks 

Publication date: 13 June 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1407.5425

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

zbMATH Keywords

communication complexityHellinger volumeinformational complexitynumber-on-the-forehead

Mathematics Subject Classification ID

Information theory (general) (94A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Elements of Information Theory
• Communication Complexity
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum communication complexity of symmetric predicates
• 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
• 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
• An information statistics approach to data stream and communication complexity
• Disjointness is hard in the multiparty number-on-the-forehead model

Cited In (1)

• Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND

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)