Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-064 | 19th June 2007 00:00

Direct Product Theorems for Communication Complexity via Subdistribution Bounds


Authors: Rahul Jain, Hartmut Klauck, Ashwin Nayak
Publication: 23rd July 2007 06:05
Downloads: 1456


A basic question in complexity theory is whether the computational
resources required for solving k independent instances of the same
problem scale as k times the resources required for one instance.
We investigate this question in various models of classical
communication complexity.

We define a new measure, the subdistribution bound, which is a
generalization of the well-studied rectangle or corruption bound in
communication complexity. We prove that the one-way version of this
bound tightly captures the one-way public-coin randomized
communication complexity of any relation. More importantly, we show
that the bound satisfies the strong direct product property under
product distributions, for both one- and two-way communication. This
way we recover and generalize, in one shot, several recent results on
the direct product question, including those due to Klauck et
al., Beame et al., Gavinsky, and de Wolf.

The simplicity and broad applicability of our technique is perhaps an
indication of its potential to solve yet more challenging questions
regarding the direct product problem.

ISSN 1433-8092 | Imprint