On Basing ZK ≠ BPP on the Hardness of PAC Learning.
David XiaoPublished in: Computational Complexity Conference (2009)
Keyphrases
- pac learning
- agnostic learning
- learning theory
- uniform distribution
- bit rate
- computational learning theory
- sample size
- sample complexity
- computational complexity
- concept classes
- membership queries
- learning problems
- decision lists
- compression ratio
- vc dimension
- worst case
- concept class
- phase transition
- statistical queries
- pac learnability
- np hard
- information theoretic
- graph cuts
- lower bound
- decision trees
- classification noise
- learning dnf