Exact query complexity of some special classes of Boolean functions.
Andris AmbainisJozef GruskaShenggen ZhengPublished in: CoRR (2014)
Keyphrases
- boolean functions
- membership queries
- query complexity
- equivalence queries
- uniform distribution
- dnf formulas
- exact learning
- dnf formulae
- term dnf
- target concept
- efficient learning
- pac learning
- read once formulas
- concept class
- learning algorithm
- boolean formula
- pattern languages
- special case
- linear threshold
- concept classes