The complexity of properly learning simple concept classes
From MaRDI portal
Publication:2462500
DOI10.1016/j.jcss.2007.04.011zbMath1151.68575MaRDI QIDQ2462500
Toniann Pitassi, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Misha Alekhnovich
Publication date: 30 November 2007
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2007.04.011
decision trees; PAC learning; proof complexity; proper learning; automatizability; DNF formulas; intersections of halfspaces; hardness of learning
68Q25: Analysis of algorithms and problem complexity
68T05: Learning and adaptive systems in artificial intelligence
68R10: Graph theory (including graph drawing) in computer science
Related Items
Hardness of approximate two-level logic minimization and PAC learning with membership queries, Special issue in memory of Misha Alekhnovich. Foreword, On the hardness of learning intersections of two halfspaces, Learning random monotone DNF
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Occam's razor
- A subexponential exact learning algorithm for DNF using equivalence queries
- The hardness of 3-uniform hypergraph coloring
- Short proofs are narrow—resolution made simple
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Learnability beyond AC 0
- Learning juntas
- A theory of the learnable
- Computational limitations on learning from examples
- Complexity of automaton identification from given data
- Randomized graph products, chromatic numbers, and Lovasz j-function
- Cryptographic limitations on learning Boolean formulae and finite automata
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds on learning decision lists and trees
- Learning DNF in time
- Cryptographic hardness of distribution-specific learning
- Exact learning of DNF formulas using DNF hypotheses