Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2008.10.014
DC FieldValue
dc.titleNew bounds on classical and quantum one-way communication complexity
dc.contributor.authorJain, R.
dc.contributor.authorZhang, S.
dc.date.accessioned2013-07-04T07:41:41Z
dc.date.available2013-07-04T07:41:41Z
dc.date.issued2009
dc.identifier.citationJain, 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
dc.identifier.issn03043975
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/39441
dc.description.abstractIn 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.tcs.2008.10.014
dc.sourceScopus
dc.subjectCommunication complexity
dc.subjectInformation theory
dc.subjectQuantum
dc.subjectRectangle bound
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1016/j.tcs.2008.10.014
dc.description.sourcetitleTheoretical Computer Science
dc.description.volume410
dc.description.issue26
dc.description.page2463-2477
dc.description.codenTCSCD
dc.identifier.isiut000267183000003
Appears in Collections:Staff Publications

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

Google ScholarTM

Check

Altmetric


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