New bounds on classical and quantum one-way communication complexity

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 epsilon is an element of (0, 1/2) be a constant. We show that for a boolean function f : x x y -> {0, 1} and a non-product distribution mu on x x y, D-epsilon(1,mu)(f) = O((I(X:Y) + 1). VC(f)). where D-epsilon(1,mu)(f) represents the one-way distributional communication complexity off with error at most epsilon under mu; VC(f) represents the Vapnik-Chervonenkis dimension of f and I(X : Y) represents the mutual information, under mu, between the random inputs of the two parties. For a non-Boolean function f : x x y ->{1.....k}(k >= 2 an integer), we show a similar upper bound on D-epsilon(1,mu)(f) in terms of k, I(X : Y) and the pseudo-dimension off'=(def) 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 off referred to as the rectangle bound or the corruption bound of f. We show for a non-boolean total function f : x x y -> Z and a product distribution is mu on x x y, Q(epsilon 3/8)(1,mu)(f) = Omega(rec(epsilon)(1,mu)(f)). where Q(epsilon 3/8)(1,mu)(f) represents the quantum one-way distributional communication complexityof f with error at most epsilon(3/8) under mu and rec(epsilon)(1,mu) (f) represents the one-way rectangle bound off with error at most E under It. Similarly for a non-Boolean partial function f : x x y -> Z boolean OR {*} and a product distribution mu on x x y, we show. Q(epsilon 6/(2.154))/(1,mu) (f) = Omega (rec(epsilon)(1,mu)(f)). (C) 2008 Elsevier B.V. All rights reserved.