A direct sum theorem in communication complexity via message compression

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen

We prove lower bounds for the direct sum problem for two-party bounded error randomised multiple-round communication protocols. Our proofs use the notion of information cost of a p…