Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function.

Published in: FOCS (2009)

Keyphrases

boolean functions
membership queries
query complexity
lower bound
upper bound
worst case
uniform distribution
special case
dnf formulas
exact learning
decision trees
active learning
vc dimension
target concept
linear threshold