Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.
Dana RonRonitt RubinfeldMuli SafraOmri WeinsteinPublished in: APPROX-RANDOM (2011)
Keyphrases
- query complexity
- monotone boolean functions
- membership queries
- uniform distribution
- concept class
- boolean functions
- exact learning
- learning algorithm
- dnf formulas
- data complexity
- concept classes
- pac learning
- equivalence queries
- target concept
- special case
- lower bound
- efficient learning
- data mining
- learning tasks
- data management
- worst case
- semi supervised