Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Julia Kempe:

TR06-086 | 25th July 2006
Dmytro Gavinsky, Julia Kempe, Ronald de Wolf

Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function

We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the ... more >>>

ISSN 1433-8092 | Imprint