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

摘要

Information-theoretic methods are a powerful tool in communication complexity, providing, in particular, elegant and tight lower bounds on disjointness in the 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). The lower bound on disjointness in the NIH model has two parts: a direct sum theorem and a lower bound on the one-bit AND function using a beautiful connection between Hellinger distance and protocols [4]. Inspired by this connection, we introduce the notion of Hellinger volume which lower bounds the information cost of multi-party NOF protocols. We provide tools for manipulating and proving lower bounds on Hellinger volume, and use these tools to obtain a lower bound on the information complexity of the ANDk function in the NOF setting. Finally, we discuss the difficulties of proving a direct sum theorem for information cost in the NOF model.