New bounds on classical and quantum one-way communication complexity

Abstract

In this paper we provide new bounds on classical and quantum distributional communication complexity in the two-party, one-way model of communication. In the classical one-way model, our bound extends the well known upper bound of Kremer, Nisan and Ron [I. Kremer, N. Nisan, D. Ron, On randomized one-round communication complexity, in: Proceedings of The 27th ACM Symposium on Theory of Computing, STOC, 1995, pp. 596-605] to include non-product distributions. Let ε{lunate} ∈ (0, 1 / 2) be a constant. We show that for a boolean function f : X × Y → {0, 1} and a non-product distribution μ on X × Y, D ε{lunate} 1, μ (f) = O ((I (X : Y) + 1) {dot operator} VC (f)), where D ε{lunate} 1, μ (f) represents the one-way distributional communication complexity of f with error at most ε{lunate} under μ; VC (f) represents the Vapnik-Chervonenkis dimension of f and I (X : Y) represents the mutual information, under μ, between the random inputs of the two parties. For a non-boolean function f : X × Y → {1, ..., k} (k ≥ 2 an integer), we show a similar upper bound on D ε{lunate} 1, μ (f) in terms of k, I (X : Y) and the pseudo-dimension of f ′ over(=, def) frac(f, k), a generalization of the VC-dimension for non-boolean functions. In the quantum one-way model we provide a lower bound on the distributional communication complexity, under product distributions, of a function f, in terms of the well studied complexity measure of f referred to as the rectangle bound or the corruption bound of f. We show for a non-boolean total function f : X × Y → Z and a product distribution μ on X × Y, Q ε{lunate}3 / 8 1, μ (f) = Ω (rec ε{lunate} 1, μ (f)), where Q ε{lunate}3 / 8 1, μ (f) represents the quantum one-way distributional communication complexity of f with error at most ε{lunate} 3 / 8 under μ and rec ε{lunate} 1, μ (f) represents the one-way rectangle bound of f with error at most ε{lunate} under μ. Similarly for a non-boolean partial function f : X × Y → Z ∪ {*} and a product distribution μ on X × Y, we show, Q ε{lunate}6 / (2 {dot operator} 1 54) 1, μ (f) = Ω (rec ε{lunate} 1, μ (f)) . © 2008 Elsevier B.V. All rights reserved.