Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-086 | 25th July 2006 00:00

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

RSS-Feed




TR06-086
Authors: Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
Publication: 25th July 2006 22:00
Downloads: 1059
Keywords: 


Abstract:

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 bounded storage model of cryptography, where the key is secure if the adversary has a certain amount of classical storage, but is completely insecure if he has a similar amount of quantum storage.



ISSN 1433-8092 | Imprint