How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
Andris AmbainisRonald de WolfPublished in: Computational Complexity Conference (2013)
Keyphrases
- boolean functions
- membership queries
- query complexity
- dnf formulae
- uniform distribution
- dnf formulas
- exact learning
- concept class
- pac learning
- equivalence queries
- target concept
- efficient learning
- data complexity
- read once formulas
- concept classes
- linear threshold
- special case
- learning algorithm
- machine learning
- semi supervised
- query answering
- boolean formula
- expressive power