Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2008.10.014
Title: New bounds on classical and quantum one-way communication complexity
Authors: Jain, R. 
Zhang, S.
Keywords: Communication complexity
Information theory
Quantum
Rectangle bound
Issue Date: 2009
Source: Jain, R., Zhang, S. (2009). New bounds on classical and quantum one-way communication complexity. Theoretical Computer Science 410 (26) : 2463-2477. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2008.10.014
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.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/39441
ISSN: 03043975
DOI: 10.1016/j.tcs.2008.10.014
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

4
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

2
checked on Dec 11, 2017

Page view(s)

59
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.