Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
Dana RonRonitt RubinfeldMuli SafraOmri WeinsteinPublished in: CoRR (2011)
Keyphrases
- boolean functions
- query complexity
- membership queries
- uniform distribution
- dnf formulas
- concept class
- exact learning
- concept classes
- pac learning
- monotone boolean functions
- target concept
- efficient learning
- disjunctive normal form
- read once formulas
- dnf formulae
- data complexity
- equivalence queries
- lower bound
- worst case
- databases
- np hard
- term dnf