Learnability beyond AC0.
Jeffrey C. JacksonAdam R. KlivansRocco A. ServedioPublished in: Computational Complexity Conference (2002)
Keyphrases
- finite automata
- boolean functions
- pattern languages
- pac learnability
- vapnik chervonenkis dimension
- learning algorithm
- dnf formulas
- inductive inference
- inductive logic programming
- uniform distribution
- uniform convergence
- pac learning
- regular languages
- efficient learning
- monotone dnf formulas
- agnostic learning
- equivalence queries
- arc consistency
- pattern matching
- cost function