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

Dmitry Gavinsky Julia Kempe Ronald de Wolf

Published in: CoRR (2006)

Keyphrases

boolean functions
uniform distribution
quantum computation
quantum mechanics
worst case
polynomial size
computational complexity
functional properties
relevant variables
pseudo boolean functions
multi valued
monotone boolean functions
np hard
statistical queries
stack filters
functional decomposition