A direct sum theorem in communication complexity via message compression

Jain, Rahul ; Radhakrishnan, Jaikumar ; Sen, Pranab (2003) A direct sum theorem in communication complexity via message compression Lecture Notes in Computer Science, 2719 . pp. 300-315. ISSN 0302-9743

PDF - Author Version

Official URL: http://www.springerlink.com/index/16dx5v0tmnybnpbn...

Related URL: http://dx.doi.org/10.1007/3-540-45061-0_26


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.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:89506
Deposited On:27 Apr 2012 13:38
Last Modified:19 May 2016 04:02

Repository Staff Only: item control page