Quantum entanglement cannot be used to achieve direct communication between
remote parties, but it can reduce the communication needed for some proble
ms. Let each of kappa parties hold some partial input data to some fixed ka
ppa-variable function f. The communication complexity off is the minimum nu
mber of classical bits required to be broadcasted for every party to know t
he value off on their inputs. We construct a function G such that for the o
ne-round communication model and three parties, G can be computed with n+l
bits of communication when the parties share prior entanglement. We then sh
ow that without entangled particles, the one-round communication complexity
of G is (3/2)n + 1. Next we generalize this function to a function F. We s
how that if the parties share prior quantum entanglement, then the communic
ation complexity of F is exactly k. We also show that, if no entangled part
icles are provided, then the communication complexity of F is roughly k log
, k. These two results prove communication complexity separations better th
an a constant number of bits. [S1050-2947(99)05209-9].