Goethe-Universität Frankfurt

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. [KvdW04], Beame et al. [BPSW07], Gavinsky [Gav06], and de Wolf [dW06]. The simplicity and broad applicability of our technique is perhaps an indication of its potential t