A direct sum theorem in communication complexity via message compression

Abstract

We prove lower bounds for the direct sum problemfor two-party bounded error randomisedmultipleround communication protocols. Our proofs use the notion of information cost of a protocol, as defined by Chakrabarti et al. [CSWY01] and refined further by Bar-Yossef et al. [BJKS02]. Our main technical result is a 'compression' theoremsaying that, for any probability distribution μ over the inputs, a k-round private coin bounded error protocol for a function ƒ with information cost c can be converted into a kround deterministic protocol for ƒ with bounded distributional error and communication cost O(kc). We prove this result using a substate theorem about relative entropy and a rejection sampling argument. Our direct sum result follows from this 'compression' result via elementary information theoretic arguments. We also consider the direct sumproblemin quantumcommunication. Using a probabilistic argument, we show thatmessages cannot be compressed in thismanner even if they carry small information. Hence, new techniques may be necessary to tackle the direct sum problem in quantum communication.