On Learning Random DNF Formulas Under the Uniform Distribution.
Jeffrey C. JacksonRocco A. ServedioPublished in: APPROX-RANDOM (2005)
Keyphrases
- uniform distribution
- term dnf
- dnf formulas
- learning dnf
- membership queries
- boolean functions
- pac model
- exact learning
- pac learning
- statistical queries
- pac learning model
- concept learning
- learning theory
- agnostic learning
- monotone dnf
- classification noise
- learning tasks
- target concept
- learning algorithm
- decision lists
- computational learning theory
- multiple instance
- phase transition
- inductive learning
- dnf formulae