A theory of the learnable
Open accessAbstract
Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense.In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming.We give a precise methodology for studying this phenomenon from a computational viewpoint.It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learned using it in a reasonable (polynomial) number of steps.Although inherent algorithmic complexity appears to set serious limits to the range of concepts that can be learned, we show that there are some important nontrivial classes of propositional concepts that can be learned in a realistic sense.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The theoretical characterization of catastrophic forgetting bounds is established through a framework grounded in PAC learning theory, enabling probabilistic guarantees on retention performance across sequential tasks.
“The theoretical characterization of catastrophic forgetting bounds is established through a rigorous framework grounded in Probably Approximately Correct (PAC) learning theory”
From Mitigating catastrophic forgetting in lifelong learning: a hybrid architecture integrating neural ordinary differential equations with memory-augmented transformers (2025) · cites this paper as [38]
Section 3 (LEARNABILITY; page unavailable) defines probabilistic guarantees for learning Boolean concepts, supporting the reference to a PAC-style framework. Neither that section nor the passages found on further search establish catastrophic-forgetting bounds or guarantees for retention across sequential tasks. (LLM, conf=0.85)
Experimental — accuracy not yet measuredThe expected performance degradation on task T_j after learning task T_i (i>j) is bounded by ε_forget(n,δ,|H|) with probability at least 1-δ.
“The forgetting bound quantifies the maximum expected performance degradation on task”
From Mitigating catastrophic forgetting in lifelong learning: a hybrid architecture integrating neural ordinary differential equations with memory-augmented transformers (2025) · cites this paper as [38]
Section 3 (LEARNABILITY; page unavailable) bounds error when learning a single program, and Section 4 (A COMBINATORIAL BOUND; page unavailable) concerns sampling. Our copy does not address performance degradation on an earlier task after learning a later one or define ε_forget(n,δ,|H|). Searches for forgetting, sequential tasks, and that bound found no relevant passage. (LLM, conf=0.76)
Experimental — accuracy not yet measuredNon-deterministic ML algorithms produce outputs expressed in probabilistic terms.
“Research focusing on inconclusive evidence refers to the way in which non-deterministic, ML algorithms produce outputs that are expressed in probabilistic terms (James et al. 2013;Valiant 1984).”
From The ethics of algorithms: key problems and solutions (2022) · cites this paper as Valiant 1984
ML algorithms generally identify association and correlation between variables in underlying data, but not causal connections.
“These types of algorithms generally identify association and correlation between variables in the underlying data, but not causal connections.”
From The ethics of algorithms: key problems and solutions (2022) · cites this paper as Valiant 1984
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385 · see citing works
Inductive Inference: Theory and Methods
Angluin, D., & Smith, C. H. (1983) · ACM Computing Surveys · doi:10.1145/356914.356918 · Cited by 872 · see citing works
A complexity theory based on Boolean algebra
Skyum, S., & Valiant, L. G. (1981) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1981.3 · Cited by 42 · see citing works
Self-citation
Flagged first, then by citations
Research works printed but not linked: 5
- Barr, A., and Feigenbaum, E.A. The Handbook of Artificial Intelligence. Vol. 2. William Kaufmann, Los Altos, Calif., 1982.
- Duda, R.O., and Hart, P.F. Pattern Classification and Scene Analysis. Wiley, New York. 1973.
- ErdSs, P., and Spencer, J. Probabilistic Methods in Combinatorics. Aca- demic Press, New York, 1974.
- Goldreich, O., Goldwasser, S., and Micali, S. How to construct ran- dom functions. In Proceedings of 25th IEEE Symposium on Foundations of Computer Science (Singer Island, Fla., Oct. 24-26). IEEE, New York, 1984.
- Valiant, L.G. Deductive learning. Philosophical Transactions of the Royal Society of London (1984). To be published. CR Categories and Subject Descriptors: F.1.1 [Computation by Ab- stract Devices[: Models of Computation; F.2.2 [Analysis of Algorithms and Problem Complexity[: Nonnumerical Algorithms and Problems; L2.6 Artificial Intelligence]: Learning--concept learning General Terms: Algorithms Additional Key Words and Phrases: inductive inference, probabilis- tic models of learning, propositional expressions
Cited by
Sorted by citations
Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170072 · Cited by 14,907 · see citing works
Approximation by superpositions of a sigmoidal function
Cybenko, G. (1989) · Mathematics of Control, Signals, and Systems · doi:10.1007/bf02551274 · Cited by 13,883 · see citing works
Machine learning: Trends, perspectives, and prospects
Jordan, M. I., & Mitchell, T. M. (2015) · Science · doi:10.1126/science.aaa8415 · Cited by 9,955 · see citing works
The capacity of wireless networks
Gupta, P., & Kumar, P. R. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.825799 · Cited by 8,192 · see citing works
Wolpert, D. H. (1992) · Neural Networks · doi:10.1016/s0893-6080(05)80023-1 · Cited by 7,951 · see citing works
Friedman, J., Hastie, T., & Tibshirani, R. (2000) · The Annals of Statistics · doi:10.1214/aos/1016218223 · Cited by 6,884 · see citing works
Instance-Based Learning Algorithms
Aha, D. W., Kibler, D. F., & Albert, M. K. (1991) · Machine Learning · doi:10.1023/a:1022689900470 · Cited by 5,217 · see citing works
Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · ACM SIGMOD Record · doi:10.1145/170036.170072 · Cited by 4,551 · see citing works
An introduction to kernel-based learning algorithms
Müller, K. R., Mika, S., Rätsch, G., Tsuda, K., & Schölkopf, B. (2001) · IEEE Transactions on Neural Networks · doi:10.1109/72.914517 · Cited by 3,485 · see citing works
The ethics of algorithms: Mapping the debate
Mittelstadt, B. D., Allo, P., Taddeo, M., Wachter, S., & Floridi, L. (2016) · Big Data & Society · doi:10.1177/2053951716679679 · Cited by 3,432 · see citing works
Human-level concept learning through probabilistic program induction
Lake, B. M., Salakhutdinov, R., & Tenenbaum, J. B. (2015) · Science · doi:10.1126/science.aab3050 · Cited by 2,817 · see citing works
Machine learning and the physical sciences
Carleo, G., Cirac, J. I., Cranmer, K. S., Daudet, L., Schuld, M., Tishby, N., Vogt-Maranto, L., & Zdeborová, L. (2019) · Reviews of Modern Physics · doi:10.1103/revmodphys.91.045002 · Cited by 2,453 · see citing works
The Strength of Weak Learnability
Schapire, R. E. (1990) · Machine Learning · doi:10.1007/bf00116037 · Cited by 4,600 · see citing works
Learning regular sets from queries and counterexamples
Angluin, D. (1987) · Information and Computation · doi:10.1016/0890-5401(87)90052-6 · Cited by 2,099 · see citing works
The Boosting Approach to Machine Learning: An Overview
Schapire, R. E. (2003) · Lecture notes in statistics · doi:10.1007/978-0-387-21579-2_9 · Cited by 2,060 · see citing works
Angluin, D. (1988) · Machine Learning · doi:10.1023/a:1022821128753 · Cited by 1,918 · see citing works
Learning in the Presence of Concept Drift and Hidden Contexts
Widmer, G., & Kubat, M. (1996) · Machine Learning · doi:10.1023/a:1018046501280 · Cited by 1,857 · see citing works
Learnability and the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989) · Journal of the ACM · doi:10.1145/76359.76371 · Cited by 1,839 · see citing works
Reed, R. (1993) · IEEE Transactions on Neural Networks · doi:10.1109/72.248452 · Cited by 1,710 · see citing works
Improving Generalization with Active Learning
Cohn, D. A., Atlas, L., & Ladner, R. E. (1994) · Machine Learning · doi:10.1023/a:1022673506211 · Cited by 1,597 · see citing works
Inductive Logic Programming: Theory and methods
Muggleton, S., & de Raedt, L. (1994) · The Journal of Logic Programming · doi:10.1016/0743-1066(94)90035-3 · Cited by 1,537 · see citing works
On the mathematical foundations of learning
Felipe Cucker, B., & Smale, S. (2001) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-01-00923-5 · Cited by 1,524 · see citing works
Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1023/a:1022869011914 · Cited by 1,514 · see citing works
Connectionist learning procedures
Hinton, G. E. (1989) · Artificial Intelligence · doi:10.1016/0004-3702(89)90049-0 · Cited by 1,487 · see citing works
Merghadi, A., Yunus, A. P., Dou, J., Whiteley, J., Pham, B. T., Bui, D. T., Avtar, R., & Boumezbeur, A. (2020) · Earth-Science Reviews · doi:10.1016/j.earscirev.2020.103225 · Cited by 1,292 · see citing works
Software unit test coverage and adequacy
Zhu, H. P., Hall, P. A. V., & May, J. H. R. (1997) · ACM Computing Surveys · doi:10.1145/267580.267590 · Cited by 1,252 · see citing works
Principles and methods of testing finite state machines-a survey
Lee, D., & Yannakakis, M. (1996) · Proceedings of the IEEE · doi:10.1109/5.533956 · Cited by 1,230 · see citing works
Human-in-the-loop machine learning: a state of the art
Mosqueira-Rey, E., Hernández-Pereira, E., Alonso-Ríos, D., Bobes-Bascarán, J., & Fernández-Leal, Á. (2022) · Artificial Intelligence Review · doi:10.1007/s10462-022-10246-w · Cited by 1,137 · see citing works
Machine learning & artificial intelligence in the quantum domain: a review of recent progress
Dunjko, V., & Briegel, H. J. (2018) · Reports on Progress in Physics · doi:10.1088/1361-6633/aab406 · Cited by 1,132 · see citing works
A perspective view and survey of meta-learning
Vilalta, R., & Drissi, Y. (2002) · Artificial Intelligence Review · doi:10.1023/a:1019956318069 · Cited by 1,108 · see citing works
Arcing classifier (with discussion and a rejoinder by the author)
Breiman, L. (1998) · The Annals of Statistics · doi:10.1214/aos/1024691079 · Cited by 1,104 · see citing works
Selective Sampling Using the Query by Committee Algorithm
Freund, Y., Seung, H. S., Shamir, E., & Tishby, N. (1997) · Machine Learning · doi:10.1023/a:1007330508534 · Cited by 1,098 · see citing works
Domain adaptation for medical image analysis: A survey
Guan, H., & Liu, M. (2022) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2021.3117407 · Cited by 1,057 · see citing works
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987) · Information Processing Letters · doi:10.1016/0020-0190(87)90114-1 · Cited by 1,054 · see citing works
Introduction to Semi-Supervised Learning
Zhu, X., & Goldberg, A. B. (2009) · Synthesis lectures on artificial intelligence and machine learning · doi:10.2200/s00196ed1v01y200906aim006 · Cited by 1,025 · see citing works
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (1998) · Journal of the ACM · doi:10.1145/285055.285060 · Cited by 1,019 · see citing works
Classifier systems and genetic algorithms
Booker, L. B., Goldberg, D. E., & Holland, J. H. (1989) · Artificial Intelligence · doi:10.1016/0004-3702(89)90050-7 · Cited by 949 · see citing works
Learning Information Extraction Rules for Semi-Structured and Free Text
Soderland, S. G. (1999) · Machine Learning · doi:10.1023/a:1007562322031 · Cited by 928 · see citing works
Interactive machine learning for health informatics: when do we need the human-in-the-loop?
Holzinger, A. (2016) · Brain Informatics · doi:10.1007/s40708-016-0042-6 · Cited by 906 · see citing works
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898 · see citing works
Rivest, R. L. (1987) · Machine Learning · doi:10.1023/a:1022607331053 · Cited by 894 · see citing works
Sparse multinomial logistic regression: fast algorithms and generalization bounds
Krishnapuram, B., Carin, L., Figueiredo, M. A. T., & Hartemink, A. J. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.127 · Cited by 872 · see citing works
Discovering models of software processes from event-based data
Cook, J., & Wolf, A. L. (1998) · ACM Transactions on Software Engineering and Methodology · doi:10.1145/287000.287001 · Cited by 870 · see citing works
Can machine learning be secure?
Barreno, M., Nelson, B. A., Sears, R., Joseph, A. D., & Tygar, J. D. (2006) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/1128817.1128824 · Cited by 852 · see citing works
Decision theoretic generalizations of the PAC model for neural net and other learning applications
Haussler, D. H. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90010-d · Cited by 845 · see citing works
Angluin, D., & Laird, P. D. (1988) · Machine Learning · doi:10.1023/a:1022873112823 · Cited by 839 · see citing works
The security of machine learning
Barreno, M., Nelson, B. A., Joseph, A. D., & Tygar, J. D. (2010) · Machine Learning · doi:10.1007/s10994-010-5188-5 · Cited by 839 · see citing works
Statistical strategies for avoiding false discoveries in metabolomics and related experiments
Broadhurst, D., & Kell, D. B. (2006) · Metabolomics · doi:10.1007/s11306-006-0037-z · Cited by 819 · see citing works
Classification with Noisy Labels by Importance Reweighting
Liu, T., & Tao, D. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2456899 · Cited by 796 · see citing works
Lowd, D., & Meek, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081950 · Cited by 755 · see citing works
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Amaldi, E., & Kann, V. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00115-1 · Cited by 744 · see citing works
Cryptographic Limitations on Learning Boolean Formulae and Finite Automata
Kearns, M. J., & Valiant, L. G. (1994) · Journal of the ACM · doi:10.1145/174644.174647 · Cited by 739 · see citing works
Self-citationDiscriminative Reranking for Natural Language Parsing
Collins, M., & Koo, T. (2005) · Computational Linguistics · doi:10.1162/0891201053630273 · Cited by 702 · see citing works
Thousands of samples are needed to generate a robust gene list for predicting outcome in cancer
Ein‐Dor, L., Zuk, O., & Domany, E. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0601231103 · Cited by 691 · see citing works
Safe Reinforcement Learning via Shielding
Alshiekh, M., Bloem, R., Ehlers, R., Könighofer, B., Niekum, S., & Topcu, U. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11797 · Cited by 37 · see citing works
Cost-sensitive learning by cost-proportionate example weighting
Zadrozny, B., Langford, J., & Abe, N. (2004) · Third IEEE International Conference on Data Mining · doi:10.1109/icdm.2003.1250950 · Cited by 680 · see citing works
Efficient noise-tolerant learning from statistical queries
Kearns, M. J. (1998) · Journal of the ACM · doi:10.1145/293347.293351 · Cited by 679 · see citing works
LERS-A System for Learning from Examples Based on Rough Sets
Grzymala‐Busse, J. W. (1992) · Springer eBooks · doi:10.1007/978-94-015-7975-9_1 · Cited by 657 · see citing works
Advance and Prospects of AdaBoost Algorithm
Cao, Y., Miao, Q., Liu, J., & Gao, L. (2013) · Acta Automatica Sinica · doi:10.1016/s1874-1029(13)60052-x · Cited by 650 · see citing works
From Boolean to probabilistic Boolean networks as models of genetic regulatory networks
Shmulevich, I., Dougherty, E. R., & Zhang, W. (2002) · Proceedings of the IEEE · doi:10.1109/jproc.2002.804686 · Cited by 631 · see citing works
On the hardness of approximate reasoning
Roth, D. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(94)00092-1 · Cited by 617 · see citing works
Cesa‐Bianchi, N., Freund, Y., Haussler, D. H., Helmbold, D. P., Schapire, R. E., & Warmuth, M. K. (1997) · Journal of the ACM · doi:10.1145/258128.258179 · Cited by 617 · see citing works
One-class classification: taxonomy of study and review of techniques
Khan, S. S., & Madden, M. G. (2014) · The Knowledge Engineering Review · doi:10.1017/s026988891300043x · Cited by 605 · see citing works
Settles, B. (2012) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.2200/s00429ed1v01y201207aim018 · Cited by 605 · see citing works
Universal Grammar, statistics or both?
Yang, C. D. (2004) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2004.08.006 · Cited by 584 · see citing works
Constant depth circuits, Fourier transform, and learnability
Linial, N., Mansour, Y., & Nisan, N. (1993) · Journal of the ACM · doi:10.1145/174130.174138 · Cited by 567 · see citing works
Wrapper induction: Efficiency and expressiveness
Kushmerick, N. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00100-9 · Cited by 550 · see citing works
FloatBoost learning and statistical face detection
Li, S. Z., & Zhang, Z. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.68 · Cited by 525 · see citing works
Unsupervised Domain Adaptation in Brain Lesion Segmentation with Adversarial Networks
Kamnitsas, K., Baumgartner, C. F., Ledig, C., Newcombe, V., Simpson, J., Kane, A. D., Menon, D. K., Nori, A., Criminisi, A., Rueckert, D., et al. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-59050-9_47 · Cited by 525 · see citing works
Finding the homology of submanifolds with high confidence from random samples
Niyogi, P., Smale, S., & Weinberger, S. (2008) · Discrete & Computational Geometry · doi:10.1007/s00454-008-9053-2 · Cited by 523 · see citing works
Hinton, G. E. (1990) · Elsevier eBooks · doi:10.1016/b978-0-08-051055-2.50029-8 · Cited by 523 · see citing works
Towards a theory of natural language interfaces to databases
Popescu, A.-M., Etzioni, O., & Kautz, H. (2003) · ACM International Conference on Intelligent User Interfaces (IUI) · doi:10.1145/604045.604070 · Cited by 522 · see citing works
Learning to Learn: Introduction and Overview
Thrun, S., & Pratt, L. (1998) · Learning to Learn · doi:10.1007/978-1-4615-5529-2_1 · Cited by 521 · see citing works
Quantum advantage in learning from experiments
Huang, H.-Y., Broughton, M., Cotler, J., Chen, S., Li, J., Mohseni, M., Neven, H., Babbush, R., Kueng, R., Preskill, J., et al. (2022) · Science · doi:10.1126/science.abn7293 · Cited by 519 · see citing works
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518 · see citing works
Statistical mechanics of learning from examples
Seung, H. S., Sompolinsky, H., & Tishby, N. (1992) · Physical Review A · doi:10.1103/physreva.45.6056 · Cited by 512 · see citing works
Computational limitations on learning from examples
Pitt, L., & Valiant, L. G. (1988) · Journal of the ACM · doi:10.1145/48014.63140 · Cited by 503 · see citing works
Self-citationKwok, T.-Y., & Yeung, D. (1997) · IEEE Transactions on Neural Networks · doi:10.1109/72.572102 · Cited by 490 · see citing works
Deep learning-based feature engineering for stock price movement prediction
Long, W., Lu, Z., & Cui, L.-X. (2018) · Knowledge-Based Systems · doi:10.1016/j.knosys.2018.10.034 · Cited by 489 · see citing works
Cunningham, P., Cord, M., & Delany, S. J. (2008) · Springer eBooks · doi:10.1007/978-3-540-75171-7_2 · Cited by 469 · see citing works
Quantifying inductive bias: AI learning algorithms and Valiant's learning framework
Haussler, D. H. (1988) · Artificial Intelligence · doi:10.1016/0004-3702(88)90002-1 · Cited by 468 · see citing works
An Introduction to Boosting and Leveraging
Meir, R., & Rätsch, G. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36434-x_4 · Cited by 454 · see citing works
Evolution of Universal Grammar
Nowak, M. A., Komarova, N. L., & Niyogi, P. (2001) · Science · doi:10.1126/science.291.5501.114 · Cited by 449 · see citing works
The Impact of Diversity on Online Ensemble Learning in the Presence of Concept Drift
Minku, L. L., White, A. P., & Yao, X. (2009) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2009.156 · Cited by 438 · see citing works
Computational and evolutionary aspects of language
Nowak, M. A., Komarova, N. L., & Niyogi, P. (2002) · Nature · doi:10.1038/nature00771 · Cited by 437 · see citing works
Tickle, A. B., Andrews, R., Golea, M., & Diederich, J. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/72.728352 · Cited by 437 · see citing works
An analysis of model-based Interval Estimation for Markov Decision Processes
Strehl, A. L., & Littman, M. L. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.08.009 · Cited by 428 · see citing works
Boolean Feature Discovery in Empirical Learning
Pagallo, G., & Haussler, D. H. (1990) · Machine Learning · doi:10.1023/a:1022611825350 · Cited by 424 · see citing works
A general lower bound on the number of examples needed for learning
Ehrenfeucht, A., Haussler, D. H., Kearns, M. J., & Valiant, L. G. (1989) · Information and Computation · doi:10.1016/0890-5401(89)90002-3 · Cited by 403 · see citing works
Self-citationTolerating noisy, irrelevant and novel attributes in instance-based learning algorithms
Aha, D. W. (1992) · International Journal of Man-Machine Studies · doi:10.1016/0020-7373(92)90018-g · Cited by 401 · see citing works
Partition testing does not inspire confidence (program testing)
Hamlet, D., & Taylor, R. (1990) · IEEE Transactions on Software Engineering · doi:10.1109/32.62448 · Cited by 394 · see citing works
Machine Learning for User Modeling
Webb, G. I., Pazzani, M. J., & Billsus, D. (2001) · User Modeling and User-Adapted Interaction · doi:10.1023/a:1011117102175 · Cited by 391 · see citing works
Probabilistic Inductive Logic Programming
Raedt, L. D., & Kersting, K. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-78652-8_1 · Cited by 386 · see citing works
A Nearest Hyperrectangle Learning Method
Salzberg, S. L. (1991) · Machine Learning · doi:10.1023/a:1022661727670 · Cited by 386 · see citing works
Arithmetic Circuits: A Survey of Recent Results and Open Questions
Shpilka, A., & Yehudayoff, A. (2009) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000039 · Cited by 385 · see citing works
The ethics of algorithms: key problems and solutions
Tsamados, A., Aggarwal, N., Cowls, J., Morley, J., Roberts, H., Taddeo, M., & Floridi, L. (2022) · AI & SOCIETY · doi:10.1007/s00146-021-01154-8 · Cited by 384 · see citing works
Distributed learning in wireless sensor networks
Predd, J. B., Kulkarni, S. R., & Poor, H. V. (2006) · IEEE Signal Processing Magazine · doi:10.1109/msp.2006.1657817 · Cited by 378 · see citing works
Efficient distribution-free learning of probabilistic concepts
Kearns, M. J., & Schapire, R. E. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80062-5 · Cited by 371 · see citing works
Number-theoretic constructions of efficient pseudo-random functions
Naor, M., & Reingold, O. (2004) · Journal of the ACM · doi:10.1145/972639.972643 · Cited by 370 · see citing works
Rademacher penalties and structural risk minimization
Koltchinskii, V. I. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.930926 · Cited by 364 · see citing works
- Authors
- Valiant, L. G.
- Affiliations
- Harvard University (US)
- Corresponding author
- Valiant, L. G.
- Venue
- Communications of the ACM
- Published
- 1984-11-05
- Volume
- 27
- Issue
- 11
- Pages
- 1134-1142
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W4238893454
- Cited by
- 3,279
- References
- 3
- Citations by year
- 2026: 58 · 2025: 93 · 2024: 117 · 2023: 106 · 2022: 123 · 2021: 116 · 2020: 96 · 2019: 91 · 2018: 89 · 2017: 94 · 2016: 89 · 2015: 84 · 2014: 62 · 2013: 91 · 2012: 71
- FWCI
- 10.16
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Communications of the ACM (publishedVersion)
- Funders
- National Science Foundation
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- learnability, concept learning, knowledge acquisition, learning protocols, information gathering, computational complexity, algorithmic complexity, computational learning theory
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
