Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.
Dana RonRonitt RubinfeldMuli SafraAlex SamorodnitskyOmri WeinsteinPublished in: ACM Trans. Comput. Theory (2012)
Keyphrases
- query complexity
- monotone boolean functions
- membership queries
- uniform distribution
- boolean functions
- learning algorithm
- dnf formulas
- concept class
- data complexity
- exact learning
- efficient learning
- pac learning
- resource consumption
- expressive power
- target concept
- image compression
- domain knowledge
- vc dimension
- resource allocation
- theoretical analysis
- equivalence queries
- upper bound
- special case
- query processing