Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution.
Michael KharitonovPublished in: J. Comput. Syst. Sci. (1995)
Keyphrases
- boolean functions
- uniform distribution
- lower bound
- concept class
- membership queries
- upper bound
- pac learning
- agnostic learning
- relevant variables
- equivalence queries
- dnf formulae
- objective function
- np hard
- dnf formulas
- optimal solution
- monotone boolean functions
- target concept
- binary decision diagrams
- upper and lower bounds
- lower and upper bounds
- polynomial size
- worst case
- exact learning
- vc dimension
- linear programming relaxation
- max sat
- statistical queries
- linear threshold
- concept classes
- target function
- linear functions
- sample complexity