Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions.

Xi Chen Jinyu Xie

Published in: SODA (2016)

Keyphrases

tight bounds
distribution free
upper bound
vc dimension
concept class
sample complexity
lower bound
normal distribution
large deviations
concept classes
sample size
pac learning
test statistic
standard deviation
learning problems
generalization bounds
worst case