AMORTIZED COMMUNICATION COMPLEXITY

In this work we study the direct-sum problem with respect to communica tion complexity: Consider a relation f defined over (0, 1)(n) x {0, 1} (n). Can the communication complexity of simultaneously computing f on l instances (x(1), y(1)),..., (x(l), y(l)) be smaller than the commun ication complexity of separately computing f on the l instances? Let t he amortized communication complexity of f be the communication comple xity of simultaneously computing f on l instances divided by l. We stu dy the properties of the amortized communication complexity. We show t hat the amortized communication complexity of a relation can be smalle r than its communication complexity. More precisely, we present a part ial function whose (deterministic) communication complexity is Theta ( log n) and amortized (deterministic) communication complexity is O(1). Similarly, for randomized protocols we present a function whose rando mized communication complexity is Theta (log n) and amortized randomiz ed communication complexity is O(1). We also give a general lower boun d on the amortized communication complexity of any function f in terms of its communication complexity C(f): for every function f the amorti zed communication complexity of f is Omega(root C(f)-log n).