A theory of the learnable

No abstract is available for this paper.

• Publication year

  1984

• Venue

  CACM

• Publication date

  Unknown publication date

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/1968.1972
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• How to construct random functions

  1986cited by this paper
• Deductive learning

  1984cited by this paper
• Inductive Inference: Theory and Methods

  1983influential reference
• A complexity theory based on Boolean algebra

  1981cited by this paper
• Pattern classification and scene analysis

  1974cited by this paper
• The complexity of theorem-proving procedures

  1971influential reference
• and Problem Complexity]: Nonnumerical Algorithms and Problems

  year unknowncited by this paper

• When Do Multi-Agent Systems Outperform? Analysing the Learning Efficiency of Agentic Systems

  2026cites this paper
• Is Multi-Distribution Learning as Easy as PAC Learning: Sharp Rates with Bounded Label Noise

  2026cites this paper
• A research agenda for active automata learning

  2026cites this paper
• All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension

  2026cites this paper
• Sample-Near-Optimal Agnostic Boosting with Improved Running Time

  2026cites this paper
• Statistical Query Lower Bounds for Smoothed Agnostic Learning

  2026cites this paper
• Anytime Safe PAC Efficient Reasoning

  2026cites this paper
• Connecting the concepts of quantum state tomography and molecular representations for machine learning

  2026cites this paper
• PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure

  2026cites this paper
• PAC-Bayesian Generalization Guarantees for Fairness on Stochastic and Deterministic Classifiers

  2026cites this paper
• ADAM-Net: Anatomy-Guided Attentive Unsupervised Domain Adaptation for Joint MG Segmentation and MGD Grading

  2026cites this paper
• Neural-Symbolic Integration with Evolvable Policies

  2026cites this paper
• Information Propagation and Encoding in Solids: A Quantitative Approach Towards Mechanical Intelligence

  2026cites this paper
• The Sample Complexity of Replicable Realizable PAC Learning

  2026cites this paper
• Learning from Synthetic Data: Limitations of ERM

  2026cites this paper
• Conditional Performance Guarantee for Large Reasoning Models

  2026cites this paper
• Quantifying and Communicating Uncertainty in SAR-Based Flood Mapping via Density-Aware Neural Networks and Conformal Risk Control

  2026cites this paper
• Distribution-Free Sequential Prediction with Abstentions

  2026influential citation
• Causal Direction from Convergence Time: Faster Training in the True Causal Direction

  2026cites this paper
• Physics-Aware Learnability: From Set-Theoretic Independence to Operational Constraints

  2026cites this paper
• Fundamentals of Quantum Machine Learning and Robustness

  2026cites this paper
• Why Code, Why Now: Learnability, Computability, and the Real Limits of Machine Learning

  2026cites this paper
• The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)

  2026cites this paper
• Minimax Rates for Hyperbolic Hierarchical Learning

  2026cites this paper
• Decision Boundary-Aware Counterfactual Learning Against Model Extraction Attacks on Graph Neural Networks

  2026cites this paper
• Complexity of deep computations via topology of function spaces

  2026cites this paper
• Group-realizable multi-group learning by minimizing empirical risk

  2026cites this paper
• Rate-Distortion Optimization for Transformer Inference

  2026cites this paper
• Bayesian Conformal Prediction as a Decision Risk Problem

  2026cites this paper
• Private Prediction via Shrinkage

  2026cites this paper
• Inference in the presence of model-form uncertainties: Leveraging a prediction-oriented approach to improve uncertainty characterization

  2026cites this paper
• Empirical Risk Minimization with f-Divergence Regularization

  2026cites this paper
• Source-Free Domain Adaptation by Optimizing Batch-Wise Cosine Similarity

  2026cites this paper
• Erzeugungsgrad, VC-dimension and neural networks with rational activation function

  2026cites this paper
• Probabilistic Performance Guarantees for Multi-Task Reinforcement Learning

  2026cites this paper
• Survey on Grammatical Inference of Formal Languages, Picture Languages

  2026cites this paper
• Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth

  2026cites this paper
• Elo-Evolve: A Co-evolutionary Framework for Language Model Alignment

  2026cites this paper
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness

  2026cites this paper
• Testable Learning of General Halfspaces under Massart Noise

  2026cites this paper
• Relatively Smart: A New Approach for Instance-Optimal Learning

  2026cites this paper
• Curvature-Weighted Capacity Allocation: A Minimum Description Length Framework for Layer-Adaptive Large Language Model Optimization

  2026cites this paper
• A dynamic model updating method for multi-scenario underwater target recognition in ocean engineering applications

  2026cites this paper
• Large Deviation Algorithms for Thresholding Bandit Problem

  2025cites this paper
• Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs

  2025cites this paper
• Experimental data re-uploading with provable enhanced learning capabilities

  2025cites this paper
• On Union-Closedness of Language Generation

  2025cites this paper
• Learning Safe Data-Driven Control Barrier Functions for Unknown Continuous Systems

  2025cites this paper
• DIM-SUM: Dynamic IMputation for Smart Utility Management

  2025cites this paper
• Boosting Double Coverage for k-Server via Imperfect Predictions

  2025cites this paper
• Universal Rates of ERM for Agnostic Learning

  2025cites this paper
• Private List Learnability vs. Online List Learnability

  2025cites this paper
• On the Hardness of Bandit Learning

  2025cites this paper
• Probably Approximately Correct Labels

  2025cites this paper
• Transition of AI Models in dependence of noise

  2025cites this paper
• Stress, strain, or displacement? A novel machine learning based framework to predict mixed mode I/II fracture load and initiation angle

  2025cites this paper
• Forecasting automobile sales with social media information under pandemic emergencies: evidence from Chinese automobile industry

  2025cites this paper
• When cells think: a neuro-symbolic view of epigenetic regulation

  2025cites this paper
• Towards Fundamental Limits for Active Multi-distribution Learning

  2025influential citation
• General Mathematical Proof of Occam's Razor; Upgrading Theoretical Physicists' Methodology

  2025cites this paper
• Probably Approximately Correct Causal Discovery

  2025cites this paper
• Simulating Evolvability as a Learning Algorithm: Empirical Investigations on Distribution Sensitivity, Robustness, and Constraint Tradeoffs

  2025cites this paper
• A Conjecture on a Fundamental Trade-Off Between Certainty and Scope in Symbolic and Generative AI

  2025cites this paper
• Agnostic Smoothed Online Learning

  2025cites this paper
• How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension

  2025cites this paper
• Witness Encryption and NP-hardness of Learning

  2025influential citation
• Semi-supervised prediction of protein fitness for data-driven protein engineering

  2025cites this paper
• Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations

  2025cites this paper
• DNF Learning via Locally Mixing Random Walks

  2025cites this paper
• When to retrain a machine learning model

  2025cites this paper
• VC-dimension of generalized progressions in some nonabelian groups

  2025cites this paper
• The Alignment Trap: Complexity Barriers

  2025cites this paper
• A Distributional-Lifting Theorem for PAC Learning

  2025cites this paper
• Bias-Aware Mislabeling Detection via Decoupled Confident Learning

  2025cites this paper
• An Effective Gram Matrix Characterizes Generalization in Deep Networks

  2025cites this paper
• The Chronicles of Foundation AI for Forensics of Multi-Agent Provenance

  2025cites this paper
• Learning Weighted Automata over Number Rings, Concretely and Categorically

  2025cites this paper
• Bayesian Leakage Analysis: A Framework for Analyzing Leakage in Cryptography

  2025cites this paper
• Example-Free Learning of Regular Languages with Prefix Queries

  2025cites this paper
• Learning in Structured Stackelberg Games

  2025cites this paper
• Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems

  2025cites this paper
• Lean Formalization of Generalization Error Bound by Rademacher Complexity

  2025cites this paper
• Can Deep Learning Models Enhance the Accuracy of Agricultural Price Forecasting? Insights From India

  2025cites this paper
• Statistical Design and Rationale of the Biomarkers for Evaluating Spine Treatments (BEST) Trial

  2025cites this paper
• Meta-learning for enhancing machines' intelligence in manufacturing

  2025cites this paper
• On Some Fundamental Problems for Multi-Agent Systems Over Multilayer Networks

  2025cites this paper
• Incentive-Aware Machine Learning; Robustness, Fairness, Improvement & Causality

  2025cites this paper
• Convex Computations for Controlled Safety Invariant Sets of Black-box Discrete-time Dynamical Systems

  2025cites this paper
• Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent

  2025cites this paper
• Data-Driven Reachability with Scenario Optimization and the Holdout Method

  2025cites this paper
• Relative-error testing of conjunctions and decision lists

  2025cites this paper
• Erzeugunsgrad, VC-Dimension and Neural Networks with rational activation function

  2025cites this paper
• A computational theory of evaluation for parameterisable subject

  2025cites this paper
• Faster Algorithms for Agnostically Learning Disjunctions and their Implications

  2025cites this paper
• An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1

  2025cites this paper
• Generalization Bounds for Quantum Learning via Rényi Divergences

  2025cites this paper
• Beyond All-to-All: Causal-Aligned Transformer with Dynamic Structure Learning for Multivariate Time Series Forecasting

  2025cites this paper
• Decoupling Representation and Learning in Genetic Programming: the LaSER Approach

  2025cites this paper
• Importance sampling for data-driven decoding of quantum error-correcting codes

  2025cites this paper
• A Learnability Analysis on Neuro-Symbolic Learning

  2025influential citation