  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.
