On basing ZK != BPP on the hardness of PAC learning.
David XiaoPublished in: Electron. Colloquium Comput. Complex. (2009)
Keyphrases
- pac learning
- agnostic learning
- learning theory
- uniform distribution
- computational learning theory
- bit rate
- sample size
- sample complexity
- pac learnability
- learning problems
- membership queries
- compression scheme
- learning dnf
- vc dimension
- computational complexity
- concept class
- boolean functions
- concept classes
- compression ratio
- worst case
- information theoretic
- image quality
- image classification
- statistical queries
- upper bound
- np hard
- feature space
- theoretical analysis
- small number
- decision lists