  We show optimal Direct Sum result for the one-way entanglement-assisted
quantum communication complexity for any relation f subset of X x Y x Z. We
show: Q^{1,pub}(f^m) = Omega(m Q^{1,pub}(f)), where Q^{1,pub}(f), represents
the one-way entanglement-assisted quantum communication complexity of f with
error at most 1/3 and f^m represents m-copies of f. Similarly for the one-way
public-coin classical communication complexity we show: R^{1,pub}(f^m) =
Omega(m R^{1,pub}(f)), where R^{1,pub}(f), represents the one-way public-coin
classical communication complexity of f with error at most 1/3. We show similar
optimal Direct Sum results for the Simultaneous Message Passing quantum and
classical models. For two-way protocols we present optimal Privacy Trade-off
results leading to a Weak Direct Sum result for such protocols. We show our
Direct Sum and Privacy Trade-off results via message compression arguments
which also imply a new round elimination lemma in quantum communication. This
allows us to extend classical lower bounds on the cell probe complexity of some
data structure problems, e.g. Approximate Nearest Neighbor Searching on the
Hamming cube {0,1}^n and Predecessor Search to the quantum setting. In a
separate result we show that Newman's technique of reducing the number of
public-coins in a classical protocol cannot be lifted to the quantum setting.
We do this by defining a general notion of black-box reduction of prior
entanglement that subsumes Newman's technique. We prove that such a black-box
reduction is impossible for quantum protocols. In the final result in the theme
of message compression, we provide an upper bound on the problem of Exact
Remote State Preparation.
