The Probably Approximately Correct Learning Model in Computational Learning Theory

This survey paper gives an overview of various known results on learning classes of Boolean functions in Valiant's Probably Approximately Correct (PAC) learning model and its commonly studied variants.

• Publication year

  2025

• Venue

  arXiv.org

• Publication date

  2025-11-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.48550/arXiv.2511.08791arXiv 2511.08791
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Superpolynomial Lower Bounds for Learning Monotone Classes

  2023cited by this paper
• Properly learning decision trees with queries is NP-hard

  2023cited by this paper
• Agnostically Learning Multi-Index Models with Queries

  2023cited by this paper
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing

  2022cited by this paper
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise

  2021cited by this paper
• From Local Pseudorandom Generators to Hardness of Learning

  2021cited by this paper
• Near-optimal lower bounds on the threshold degree and sign-rank of AC0

  2019cited by this paper
• Hardness of learning DNFs using halfspaces

  2019cited by this paper
• Tight bounds on The Fourier Spectrum of AC0

  2017cited by this paper
• A Nearly Optimal Lower Bound on the Approximate Degree of AC^0

  2017cited by this paper
• Learning Algorithms from Natural Proofs

  2016cited by this paper
• Natural proofs

  2016cited by this paper
• The Power of Asymmetry in Constant-Depth Circuits

  2015cited by this paper
• How to Refute a Random CSP

  2015cited by this paper
• Complexity theoretic limitations on learning halfspaces

  2015cited by this paper
• Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem

  2015influential reference
• Complexity Theoretic Limitations on Learning DNF's

  2014cited by this paper
• Understanding Machine Learning - From Theory to Algorithms

  2014cited by this paper
• Learning circuits with few negations

  2014cited by this paper
• Preserving Statistical Validity in Adaptive Data Analysis

  2014cited by this paper
• Breaking the minsky-papert barrier for constant-depth circuits

  2014cited by this paper
• The power of localization for efficiently learning linear separators with noise

  2013cited by this paper
• Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching

  2013cited by this paper
• Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World

  2013cited by this paper
• Boosting: Foundations and Algorithms

  2013cited by this paper
• Learning DNF Expressions from Fourier Spectrum

  2012cited by this paper
• The correct exponent for the Gotsman–Linial Conjecture

  2012cited by this paper
• Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces

  2012cited by this paper
• Analysis of Boolean Functions

  2012cited by this paper
• On the hardness of learning intersections of two halfspaces

  2011cited by this paper
• A random-sampling-based algorithm for learning intersections of halfspaces

  2010cited by this paper
• Learning and Lower Bounds for AC0 with Threshold Gates

  2010cited by this paper
• Public-key cryptography from different assumptions

  2010cited by this paper
• Hardness results for agnostically learning low-degree polynomial threshold functions

  2010cited by this paper
• Pseudorandom generators for polynomial threshold functions

  2009cited by this paper
• A Complete Characterization of Statistical Query Learning with Applications to Evolvability

  2009cited by this paper
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function

  2009cited by this paper
• Characterizing Statistical Query Learning: Simplified Notions and Proofs

  2009cited by this paper
• The Intersection of Two Halfspaces Has High Threshold Degree

  2009cited by this paper
• KKL, Kruskal-Katona, and Monotone Nets

  2009cited by this paper
• A note on the sign degree of formulas

  2009cited by this paper
• Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions

  2009cited by this paper
• Learning Halfspaces with Malicious Noise

  2009cited by this paper
• Bounding the Sensitivity of Polynomial Threshold Functions

  2009cited by this paper
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

  2009cited by this paper
• Potential-Based Agnostic Boosting

  2009cited by this paper
• Distribution-Specific Agnostic Boosting

  2009cited by this paper
• Agnostically learning decision trees

  2008cited by this paper
• The chow parameters problem

  2008cited by this paper
• The complexity of properly learning simple concept classes

  2008cited by this paper
• Learning Geometric Concepts via Gaussian Surface Area

  2008cited by this paper
• Evolvability from learning algorithms

  2008cited by this paper
• A Brief Introduction to Fourier Analysis on the Boolean Cube

  2008cited by this paper
• Hardness of Minimizing and Learning DNF Expressions

  2008cited by this paper
• A Quantum Algorithm for the Hamiltonian NAND Tree

  2007cited by this paper
• A Characterization of Strong Learnability in the Statistical Query Model

  2007cited by this paper
• Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer

  2007cited by this paper
• Hardness of Reconstructing Multivariate Polynomials over Finite Fields

  2007cited by this paper
• Span-program-based quantum algorithm for evaluating formulas

  2007cited by this paper
• New Results for Learning Noisy Parities and Halfspaces

  2006cited by this paper
• Hardness of Learning Halfspaces with Noise

  2006cited by this paper
• Calibrating Noise to Sensitivity in Private Data Analysis

  2006cited by this paper
• Learning monotone decision trees in polynomial time

  2006cited by this paper
• Cryptographic Hardness for Learning Intersections of Halfspaces

  2006cited by this paper
• Hardness of approximate two-level logic minimization and PAC learning with membership queries

  2006cited by this paper
• Estimation of Dependences Based on Empirical Data

  2006cited by this paper
• Evolvability

  2006cited by this paper
• On lattices, learning with errors, random linear codes, and cryptography

  2005cited by this paper
• Practical privacy: the SuLQ framework

  2005cited by this paper
• An algorithm to learn read-once threshold formulas, and transformations between learning models

  2005cited by this paper
• Toward efficient agnostic learning

  2004influential reference
• Learning functions of k relevant variables

  2004influential reference
• Learning decision lists

  2004cited by this paper
• New lattice based cryptographic constructions

  2003cited by this paper
• Relations between average case complexity and approximation complexity

  2002cited by this paper
• Learning intersections and thresholds of halfspaces

  2002influential reference
• Learning DNF in time 2 Õ(n 1/3 ) .

  2001cited by this paper
• Agnostic Learning of Geometric Patterns

  2001cited by this paper
• A Slight Sharpening of LMN

  2001cited by this paper
• On learning monotone DNF under product distributions

  2001cited by this paper
• Learning functions represented as multiplicity automata

  2000influential reference
• Noise-tolerant learning, the parity problem, and the statistical query model

  2000cited by this paper
• On the difficulty of approximately maximizing agreements

  2000cited by this paper
• A Pseudorandom Generator from any One-way Function

  1999cited by this paper
• Learning DNF by approximating inclusion-exclusion formulae

  1999cited by this paper
• A Short Introduction to Boosting

  1999cited by this paper
• Bounds for small-error and zero-error quantum algorithms

  1999cited by this paper
• PAC Learning Intersections of Halfspaces with Membership Queries

  1998cited by this paper
• On learning monotone Boolean functions

  1998cited by this paper
• Efficient noise-tolerant learning from statistical queries

  1998influential reference
• Learning an Intersection of a Constant Number of Halfspaces over a Uniform Distribution

  1997cited by this paper
• Number-theoretic constructions of efficient pseudo-random functions

  1997cited by this paper
• A decision-theoretic generalization of on-line learning and an application to boosting

  1997cited by this paper
• On the Fourier spectrum of monotone functions

  1996cited by this paper
• A simple algorithm for learning O(log n)-term DNF

  1996cited by this paper
• On Restricted-Focus-of-Attention Learnability of Boolean Functions

  1996cited by this paper
• A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries

  1996cited by this paper
• On Learning μ-Perceptron Networks On the Uniform Distribution ∗

  1995cited by this paper
• Theory and Applications of Agnostic PAC-Learning with Small Decision Trees

  1995cited by this paper
• Learning Boolean Read-Once Formulas over Generalized Bases

  1995cited by this paper

• Connecting the concepts of quantum state tomography and molecular representations for machine learning

  2026cites this paper