A lower bound on the quantum query complexity of read-once functions

Howard Barnum Michael E. Saks

Published in: Electron. Colloquium Comput. Complex. (2002)

Keyphrases

lower bound
query complexity
concept class
upper bound
dnf formulas
equivalence queries
membership queries
vc dimension
exact learning
max sat
concept classes
learning theory
read once formulas
data complexity
statistical queries
optimal solution
objective function
boolean functions
np hard
machine learning