Amortized Communication Complexity

In this work we study the direct-sum problem with respect to communication complexity: Consider a relation f defined over \0,1\ⁿ × \0,1\ⁿ. Can the communication complexity of simultaneously computing f on instances (x₁, y₁), , (x_, y_) be smaller than the communication complexity of separately computing f on the instances? Let the amortized communication complexity of f be the communication complexity of simultaneously computing f on instances divided by . We study the properties of the amortized communication complexity. We show that the amortized communication complexity of a relation can be smaller than its communication complexity. More precisely, we present a partial function whose (deterministic) communication complexity is Θ (log n) and amortized (deterministic) communication complexity is $O(1)$. Similarly, for randomized protocols we present a function whose randomized communication complexity is Θ (log n) and amortized randomized communication complexity is $O(1)$. We also give a general lower bound on the amortized communication complexity of any functionf in terms of its communication complexity $C(f)$: for every function f the amortized communication complexity of f is Ω (√C(f) - log n).