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 ϵ∈(0,1/2)ϵ∈(0,1/2) be a constant. We show that for a boolean function f:X×Y→{0,1}f:X×Y→{0,1} and a non-product distribution μμ on X×YX×Y, Dϵ1,μ(f)=O((I(X:Y)+1)⋅VC(f)), where Dϵ1,μ(f) represents the one-way distributional communication complexity of ff with error at most ϵϵ under μμ; VC(f) represents the Vapnik–Chervonenkis   dimension of ff and I(X:Y)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}f:X×Y→{1,…,k} (k≥2k≥2 an integer), we show a similar upper bound on Dϵ1,μ(f) in terms of k,I(X:Y)k,I(X:Y) and the pseudo-dimension   of f′=deffk, 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 ff, in terms of the well studied complexity measure of ff referred to as the rectangle bound or the corruption bound   of ff. We show for a non-boolean total function f:X×Y→Zf:X×Y→Z and a product distribution μμ on X×YX×Y, Qϵ3/81,μ(f)=Ω(recϵ1,μ(f)), where Qϵ3/81,μ(f) represents the quantum one-way distributional communication complexity of ff with error at most ϵ3/8ϵ3/8 under μμ and recϵ1,μ(f) represents the one-way rectangle bound of ff with error at most ϵϵ under μμ. Similarly for a non-boolean partial function f:X×Y→Z∪{∗}f:X×Y→Z∪{∗} and a product distribution μμ on X×YX×Y, we show, Qϵ6/(2⋅154)1,μ(f)=Ω(recϵ1,μ(f)).