Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function.
Dmitry GavinskyJulia KempeRonald de WolfPublished in: Electron. Colloquium Comput. Complex. (2006)
Keyphrases
- boolean functions
- uniform distribution
- polynomial size
- quantum computation
- worst case
- membership queries
- relevant variables
- quantum mechanics
- computational complexity
- stack filters
- read once formulas
- functional decomposition
- functional properties
- dnf formulas
- bounded treewidth
- bayesian networks
- classification algorithm
- nearest neighbor
- search algorithm