Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
From MaRDI portal
Publication:5892607
DOI10.1007/978-3-642-22006-7_35zbMath1332.68100OpenAlexW63374407MaRDI QIDQ5892607
Ryan C. Harkins, John M. Hitchcock
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_35
Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Almost everywhere high nonuniform complexity
- Complexity theoretic hardness results for query learning
- Mathematical metaphysics of randomness
- Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
- Resource-bounded measure and learnability
- Efficient learning algorithms yield circuit lower bounds
- Kolmogorov-Loveland randomness and stochasticity
- PP is as Hard as the Polynomial-Time Hierarchy
- A theory of the learnable
- Cryptographic limitations on learning Boolean formulae and finite automata
- A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
- Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
This page was built for publication: Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
