The complexity of properly learning simple concept classes

DOI10.1016/j.jcss.2007.04.011zbMath1151.68575OpenAlexW1990948892MaRDI QIDQ2462500

Toniann Pitassi, Vitaly Feldman, Adam R. Klivans, Misha Alekhnovich, Mark Braverman

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 treesPAC learningproof complexityproper learningautomatizabilityDNF formulasintersections of halfspaceshardness of learning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

Exact learning from an honest teacher that answers membership queries ⋮ On the hardness of learning intersections of two halfspaces ⋮ Learning random monotone DNF ⋮ Special issue in memory of Misha Alekhnovich. Foreword ⋮ PCPs and the hardness of generating synthetic data ⋮ The hardest halfspace ⋮ On the structure of Boolean functions with small spectral norm ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ Hardness of approximate two-level logic minimization and PAC learning with membership queries

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

This page was built for publication: The complexity of properly learning simple concept classes