Expected query complexity of symmetric boolean functions.
Jayadev AcharyaAshkan JafarpourAlon OrlitskyPublished in: Allerton (2011)
Keyphrases
- boolean functions
- membership queries
- query complexity
- uniform distribution
- dnf formulas
- exact learning
- pac learning
- efficient learning
- read once formulas
- target concept
- equivalence queries
- dnf formulae
- concept class
- data complexity
- concept classes
- pattern languages
- positive and negative
- linear threshold
- decision trees
- machine learning