Distribution-Free Testing Lower Bound for Basic Boolean Functions.
Dana GlasnerRocco A. ServedioPublished in: Theory Comput. (2009)
Keyphrases
- boolean functions
- distribution free
- concept class
- membership queries
- lower bound
- uniform distribution
- vc dimension
- upper bound
- concept classes
- pac learning
- sample complexity
- learning theory
- target concept
- efficient learning
- normal distribution
- large deviations
- concept learning
- statistical queries
- theoretical analysis
- learning algorithm