Mansour's Conjecture is True for Random DNF Formulas.
Adam R. KlivansHomin K. LeeAndrew WanPublished in: Electron. Colloquium Comput. Complex. (2010)
Keyphrases
- dnf formulas
- pac model
- membership queries
- classification noise
- randomly chosen
- uniform distribution
- upper and lower bounds
- concept class
- monotone dnf
- boolean functions
- pac learning
- truth table
- monotone dnf formulas
- statistical queries
- concept classes
- equivalence queries
- term dnf
- learning dnf
- conjunctive queries
- efficient learning
- sample complexity