Distribution-Free Testing Lower Bounds for Basic Boolean Functions.
Dana GlasnerRocco A. ServedioPublished in: APPROX-RANDOM (2007)
Keyphrases
- boolean functions
- distribution free
- concept class
- membership queries
- uniform distribution
- vc dimension
- lower bound
- pac learning
- upper bound
- target concept
- concept classes
- sample complexity
- efficient learning
- learning theory
- normal distribution
- objective function
- worst case
- large deviations
- optimal solution
- compression scheme
- sample size