Mansour's Conjecture is True for Random DNF Formulas.
Adam R. KlivansHomin K. LeeAndrew WanPublished in: COLT (2010)
Keyphrases
- dnf formulas
- pac model
- membership queries
- classification noise
- uniform distribution
- randomly chosen
- monotone dnf formulas
- concept class
- monotone dnf
- pac learning
- boolean functions
- learning theory
- concept classes
- statistical queries
- upper and lower bounds
- conjunctive queries
- agnostic learning
- lower bound
- truth table
- learning dnf
- decision lists
- noise tolerant
- efficient learning
- upper bound