The Complexity of DNF of Parities.
Gil CohenIgor ShinkarPublished in: Electron. Colloquium Comput. Complex. (2014)
Keyphrases
- uniform distribution
- boolean functions
- membership queries
- agnostic learning
- noise tolerant
- pac learning
- learning theory
- attribute efficient learning
- learning dnf
- disjunctive normal form
- decision lists
- worst case
- polynomial size
- dnf formulas
- learning algorithm
- statistical queries
- boolean formula
- exact learning
- multiple instance
- boosting algorithms
- classification noise
- target concept
- decision rules