Please use this identifier to cite or link to this item:
Title: New results in the simultaneous message passing model via information theoretic techniques
Authors: Jain, R. 
Klauck, H.
Keywords: Communication Complexity
Direct sum
Information theory
Simultaneous message passing
Issue Date: 2009
Citation: Jain, R., Klauck, H. (2009). New results in the simultaneous message passing model via information theoretic techniques. Proceedings of the Annual IEEE Conference on Computational Complexity : 369-378. ScholarBank@NUS Repository.
Abstract: Consider the following Simultaneous Message Passing (SMP) model for computing a relation f ⊆ X × Y × ℤ. in this model Alice, on input x ∈ X and Bob, on input y ∈ Y, send one message each to a third party Referee who then outputs a z ∈ ℤ such that (x, y, z) ∈ f. We first show optimal Direct sum results for all relations f in this model, both in the quantum and classical settings, in the situation where we allow shared resources (shared entanglement in quantum protocols and public coins in classical protocols) between Alice and Referee and Bob and Referee and no shared resource between Alice and Bob. This implies that, in this model, the communication required to compute k simultaneous instances of f, with constant success overall, is at least k-times the communication required to compute one instance with constant success. This in particular implies an earlier Direct sum result, shown by Chakrabarti, Shi, Wirth and Yao [CSWY01] for the Equality function (and a class of other so-called robust functions), in the classical SMP model with no shared resources between any parties. Furthermore we investigate the gap between the SMP model and the one-way model in communication complexity and exhibit a partial function that is exponentially more expensive in the former if quantum communication with entanglement is allowed, compared to the latter even in the deterministic case. © 2009 IEEE.
Source Title: Proceedings of the Annual IEEE Conference on Computational Complexity
ISBN: 9780769537177
ISSN: 10930159
DOI: 10.1109/CCC.2009.28
Appears in Collections:Staff Publications

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


checked on Dec 4, 2019


checked on Nov 27, 2019

Page view(s)

checked on Dec 2, 2019

Google ScholarTM



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