The complexity of properly learning simple concept classes

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

zbMATH Keywords

decision trees; PAC learning; proof complexity; proper learning; automatizability; DNF formulas; intersections of halfspaces; hardness of learning

Mathematics Subject Classification ID

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, 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 ⁰
• 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