Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function.

Ben W. Reichardt

Published in: CoRR (2009)

Keyphrases

boolean functions
membership queries
query complexity
upper bound
lower bound
uniform distribution
dnf formulas
special case
dnf formulae
worst case
machine learning
vc dimension
concept class
exact learning
linear threshold
read once formulas