Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-074 | 7th August 2007 00:00

Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity

RSS-Feed




TR07-074
Authors: Dmytro Gavinsky, Pavel Pudlak
Publication: 8th August 2007 13:33
Downloads: 3060
Keywords: 


Abstract:

We give the first exponential separation between quantum and
classical multi-party
communication complexity in the (non-interactive) one-way and
simultaneous message
passing settings.
For every k, we demonstrate a relational communication problem
between k parties
that can be solved exactly by a quantum simultaneous message passing
protocol of
cost O(log n) and requires protocols of cost n^{c/k^2}, where c>0 is a
constant, in the
classical non-interactive one-way message passing model with shared randomn=
ess
and bounded error. Thus our separation of corresponding communication
classes is
superpolynomial as long as k=3Do(\sqrt{\log n / \log\log n}) and
exponential for k=3DO(1).



ISSN 1433-8092 | Imprint