The quantum query complexity of certification.

Andris Ambainis Andrew M. Childs François Le Gall Seiichiro Tani

Published in: Quantum Inf. Comput. (2010)

Keyphrases

query complexity
data complexity
membership queries
exact learning
dnf formulas
concept class
query answering
vc dimension
dnf formulae
learning algorithm
expressive power