Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with NOF:
TR07-074 | 7th August 2007
Dmitry Gavinsky, Pavel Pudlak

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

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 ... more >>>

ISSN 1433-8092 | Imprint