How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?

Andris Ambainis Ronald de Wolf

Published in: Comput. Complex. (2014)

Keyphrases

boolean functions
membership queries
query complexity
dnf formulae
uniform distribution
dnf formulas
exact learning
concept class
pac learning
efficient learning
equivalence queries
target concept
read once formulas
concept classes
data complexity
linear threshold
disjunctive normal form
term dnf
pattern languages