Abstract:
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.