Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution.
Michael KharitonovPublished in: COLT (1992)
Keyphrases
- boolean functions
- uniform distribution
- lower bound
- concept class
- membership queries
- upper bound
- pac learning
- agnostic learning
- relevant variables
- dnf formulas
- target concept
- equivalence queries
- np hard
- statistical queries
- optimal solution
- dnf formulae
- monotone boolean functions
- upper and lower bounds
- worst case
- concept classes
- term dnf
- max sat
- lower and upper bounds
- disjunctive normal form
- linear programming relaxation
- binary decision diagrams
- vc dimension
- polynomial size
- theoretical analysis
- np complete