Cited by 3,279Machine Learning and AlgorithmsComputability, Logic, AI Algorithmssemigroups and automata theory

The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.

A theory of the learnable

Open access

Valiant, L. G.·1984·Communications of the ACM

DOI 10.1145/1968.1972

Open this paper in CoChat — free account Open PDF

Abstract

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

Crossref · 10.1145/1968.1972

Cites

3 of 3 references verified0 citation errors · 0 not checkable

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?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

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
Inductive Inference: Theory and Methods
Angluin, D., & Smith, C. H. (1983) · ACM Computing Surveys · doi:10.1145/356914.356918 · Cited by 872
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
Self-citation

Flagged first, then by citations

Show all 3 references

Research works printed but not linked: 6

Barr A., 1982, Calif.
Duda R.O. and Hart P.F. Pattern Classification and Scene Analysis. Wiley New York. 1973. Duda R.O. and Hart P.F. Pattern Classification and Scene Analysis. Wiley New York. 1973.
ErdSs P., 1974, Academic Press
Goldreich O., 1984, Proceedings of 25th IEEE Symposium on Foundations of Computer Science (Singer Island, Fla., Oct. 24-26)
Michalski R.S., 1983, Calif.
Valiant L.G. Deductive learning. Philosophical Transactions of the Royal Society of London (1984). To be published. Valiant L.G. Deductive learning. Philosophical Transactions of the Royal Society of London (1984). To be published.

Sorted by citations

Items 201–300 of 1,004

Application of new deep genetic cascade ensemble of SVM classifiers to predict the Australian credit scoring
Pławiak, P., Abdar, M., & Acharya, U. R. (2019) · Applied Soft Computing · doi:10.1016/j.asoc.2019.105740 · Cited by 177
Toward Efficient Agnostic Learning
Kearns, M. J., Schapire, R. E., & Sellie, L. M. (1994) · Machine Learning · doi:10.1007/bf00993468 · Cited by 172
Theoretical Views of Boosting and Applications
Schapire, R. E. (1999) · Lecture notes in computer science · doi:10.1007/3-540-46769-6_2 · Cited by 171
Algorithms for Identifying Boolean Networks and Related Biological Networks Based on Matrix Multiplication and Fingerprint Function
Akutsu, T., Miyano, S., & Kuhara, S. (2000) · Journal of Computational Biology · doi:10.1089/106652700750050817 · Cited by 169
Learning with Maximum-Entropy Distributions
Mansour, Y., & Schain, M. (2001) · Machine Learning · doi:10.1023/a:1010950718922 · Cited by 168
Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions
Naor, M., & Reingold, O. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1618 · Cited by 168
Learning Conjunctive Concepts in Structural Domains
Haussler, D. H. (1989) · Machine Learning · doi:10.1023/a:1022601210986 · Cited by 167
Neural net algorithms that learn in polynomial time from examples and queries
Baum, E. B. (1991) · IEEE Transactions on Neural Networks · doi:10.1109/72.80287 · Cited by 166
Applications of Machine Learning Methods to Genomic Selection in Breeding Wheat for Rust Resistance
González‐Camacho, J. M., Ornella, L., Pérez‐Rodríguez, P., Gianola, D., Dreisigacker, S., & Crossa, J. L. (2018) · The Plant Genome · doi:10.3835/plantgenome2017.11.0104 · Cited by 170
Artificial Intelligence
Poole, D., & Mackworth, A. K. (2017) · Cambridge University Press eBooks · doi:10.1017/9781108164085 · Cited by 173
A discriminative framework for clustering via similarity functions
Balcan, M.-F., Blum, A. L., & Vempala, S. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374474 · Cited by 163
On-Line Algorithms in Machine Learning
Blum, A. L. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029575 · Cited by 162
Learning cost-sensitive active classifiers☆☆This extends the short conference paper [19].
Greiner, R., Grove, A. J., & Roth, D. (2002) · Artificial Intelligence · doi:10.1016/s0004-3702(02)00209-6 · Cited by 162
Parameterized Computational Feasibility
Downey, R. G., & Fellows, M. R. (1995) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4612-2566-9_7 · Cited by 162
Machine Learning in a Quantum World
Aı̈meur, E., Gilles Brassard, A., & Gambs, S. (2006) · Lecture notes in computer science · doi:10.1007/11766247_37 · Cited by 161
Computational aspects of monotone dualization: A brief survey
Eiter, T., Makino, K., & Gottlob, G. (2007) · Discrete Applied Mathematics · doi:10.1016/j.dam.2007.04.017 · Cited by 161
Tracking Drifting Concepts By Minimizing Disagreements
Helmbold, D. P., & Long, P. M. (1994) · Machine Learning · doi:10.1023/a:1022694620923 · Cited by 161
Combinations of weak classifiers
Ji, C., & Ma, S. (1997) · IEEE Transactions on Neural Networks · doi:10.1109/72.554189 · Cited by 159
Learning pattern classification-a survey
Kulkarni, S. R., Lugosi, G., & Venkatesh, S. S. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720536 · Cited by 161
On the Accuracy of Meta-learning for Scalable Data Mining
Chan, P. K., & Stolfo, S. J. (1997) · Journal of Intelligent Information Systems · doi:10.1023/a:1008640732416 · Cited by 158
Efficiently learning mixtures of two Gaussians
Kalai, A. T., Moitra, A., & Valiant, G. J. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806765 · Cited by 157
Quantum machine learning for chemistry and physics
Sajjan, M., Li, J., Selvarajan, R., Sureshbabu, S. H., Kale, S. S., Gupta, R., Singh, V., & Kais, S. (2022) · Chemical Society Reviews · doi:10.1039/d2cs00203e · Cited by 173
Recent advances of grammatical inference
Sakakibara, Y. (1997) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00014-5 · Cited by 156
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey
Lugosi, G., & Mendelson, S. (2019) · Foundations of Computational Mathematics · doi:10.1007/s10208-019-09427-x · Cited by 154
Instance‐based prediction of real‐valued attributes
Kibler, D. F., Aha, D. W., & Albert, M. K. (1989) · Computational Intelligence · doi:10.1111/j.1467-8640.1989.tb00315.x · Cited by 154
Binary Ensemble Neural Network: More Bits per Network or More Networks per Bit?
Zhu, S., Dong, X., & Su, H. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.00506 · Cited by 153
On the Complexity of Computing and Learning with Multiplicative Neural Networks
Schmitt, M. (2002) · Neural Computation · doi:10.1162/08997660252741121 · Cited by 154
The minimum consistent DFA problem cannot be approximated within any polynomial
Pitt, L., & Warmuth, M. K. (1993) · Journal of the ACM · doi:10.1145/138027.138042 · Cited by 153
Guest Column: A Survey of Quantum Learning Theory
Arunachalam, S., & de Wolf, R. (2017) · ACM SIGACT News · doi:10.1145/3106700.3106710 · Cited by 152
Novel genetic ensembles of classifiers applied to myocardium dysfunction recognition based on ECG signals
Pławiak, P. (2017) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2017.10.002 · Cited by 154
Learning from examples in large neural networks
Sompolinsky, H., Tishby, N., & Seung, H. S. (1990) · Physical Review Letters · doi:10.1103/physrevlett.65.1683 · Cited by 152
Query-based learning applied to partially trained multilayer perceptrons
Hwang, J., Choi, J. J., Oh, S., & Marks, R. J. (1991) · IEEE Transactions on Neural Networks · doi:10.1109/72.80299 · Cited by 152
The Vapnik-Chervonenkis Dimension: Information versus Complexity in Learning
Abu‐Mostafa, Y. S. (1989) · Neural Computation · doi:10.1162/neco.1989.1.3.312 · Cited by 151
Learning the CLASSIC Description Logic: Theoretical and Experimental Results
Cohen, W. W., & Hirsh, H. (1994) · Principles of Knowledge Representation and Reasoning · doi:10.1016/b978-1-4832-1452-8.50108-1 · Cited by 150
Diversity Regularized Ensemble Pruning
Li, N., Yu, Y., & Zhou, Z. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33460-3_27 · Cited by 153
Metric Learning
Bellet, A., Habrard, A., & Sebban, M. (2015) · Synthesis lectures on artificial intelligence and machine learning · doi:10.2200/s00626ed1v01y201501aim030 · Cited by 164
Logical settings for concept-learning
Raedt, L. D. (1997) · Artificial Intelligence · doi:10.1016/s0004-3702(97)00041-6 · Cited by 154
Nonparametric estimation via empirical risk minimization
Lugosi, G., & Zeger, K. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.382014 · Cited by 147
Efficient agnostic learning of neural networks with bounded fan-in
Lee, W. S., Bartlett, P. L., & Williamson, R. C. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556601 · Cited by 147
Multi-site MRI harmonization via attention-guided deep domain adaptation for brain disorder identification
Guan, H., Liu, Y., Yang, E., Yap, P., Shen, D. G., & Liu, M. (2021) · Medical Image Analysis · doi:10.1016/j.media.2021.102076 · Cited by 153
The Evolutionary Dynamics of Grammar Acquisition
Komarova, N. L., Niyogi, P., & Nowak, M. A. (2001) · Journal of Theoretical Biology · doi:10.1006/jtbi.2000.2240 · Cited by 152
Four Types of Learning Curves
Амари, Ш.-И., Fujita, N., & Shinomoto, S. (1992) · Neural Computation · doi:10.1162/neco.1992.4.4.605 · Cited by 144
Agnostic Learning of Monomials by Halfspaces Is Hard
Feldman, V., Guruswami, V., Raghavendra, P., & Wu, Y. (2012) · SIAM Journal on Computing · doi:10.1137/120865094 · Cited by 143
Learning decision trees from random examples
Ehrenfeucht, A., & Haussler, D. H. (1989) · Information and Computation · doi:10.1016/0890-5401(89)90001-1 · Cited by 143
New Results for Learning Noisy Parities and Halfspaces
Feldman, V., Gopalan, P., Khot, S., & Ponnuswami, A. K. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.51 · Cited by 142
Selecting concise training sets from clean data
Plutowski, M., & White, H. (1993) · IEEE Transactions on Neural Networks · doi:10.1109/72.207618 · Cited by 141
A theory of learning with similarity functions
Balcan, M.-F., Blum, A. L., & Srebro, N. (2008) · Machine Learning · doi:10.1007/s10994-008-5059-5 · Cited by 140
Linear approximation of shortest superstrings
Blum, A. L., Jiang, T., Li, M., Tromp, J., & Yannakakis, M. (1994) · Journal of the ACM · doi:10.1145/179812.179818 · Cited by 140
From On-line to Batch Learning
Littlestone, N. (1989) · Elsevier eBooks · doi:10.1016/b978-0-08-094829-4.50022-2 · Cited by 140
First-order jk-clausal theories are PAC-learnable
Raedt, L. D., & Džeroski, S. (1994) · Artificial Intelligence · doi:10.1016/0004-3702(94)90112-0 · Cited by 140
Prediction-preserving reducibility
Pitt, L., & Warmuth, M. K. (1990) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(90)90028-j · Cited by 140
Cryptography and machine learning
Rivest, R. L. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57332-1_36 · Cited by 138
Discovering Neural Nets with Low Kolmogorov Complexity and High Generalization Capability
Schmidhuber, J. (1997) · Neural Networks · doi:10.1016/s0893-6080(96)00127-x · Cited by 148
No better ways to generate hard NP instances than picking uniformly at random
Impagliazzo, R., & Levin, L. A. (1990) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89604 · Cited by 137
Statistical Theory of Learning Curves under Entropic Loss Criterion
Амари, Ш.-И., & Murata, N. (1993) · Neural Computation · doi:10.1162/neco.1993.5.1.140 · Cited by 134
Equivalence of models for polynomial learnability
Haussler, D. H., Kearns, M. J., Littlestone, N., & Warmuth, M. K. (1991) · Information and Computation · doi:10.1016/0890-5401(91)90042-z · Cited by 133
Property Testing: A Learning Theory Perspective
Ron, D. (2008) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000004 · Cited by 132
A Tutorial on Meta-Reinforcement Learning
Beck, J., Vuorio, R., Liu, E. Z., Xiong, Z., Zintgraf, L., Finn, C., & Whiteson, S. (2025) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000080 · Cited by 270
Optimal generalization in perceptions
Kinouchi, O., & Caticha, N. (1992) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/25/23/020 · Cited by 132
Structure identification in relational data
Dechter, R., & Pearl, J. (1992) · Artificial Intelligence · doi:10.1016/0004-3702(92)90009-m · Cited by 130
Screening billions of candidates for solid lithium-ion conductors: A transfer learning approach for small data
Cubuk, E. D., Sendek, A. D., & Reed, E. J. (2019) · The Journal of Chemical Physics · doi:10.1063/1.5093220 · Cited by 131
Inferring extended finite state machine models from software executions
Walkinshaw, N., Taylor, R., & Derrick, J. (2016) · Empirical Software Engineering · doi:10.1007/s10664-015-9367-7 · Cited by 127
Knows what it knows: a framework for self-aware learning
Li, L. C., Littman, M. L., Walsh, T. J., & Strehl, A. L. (2010) · Machine Learning · doi:10.1007/s10994-010-5225-4 · Cited by 127
Competitive recommendation systems
Petros Drineas, B., Kerenidis, I., & Raghavan, P. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509922 · Cited by 127
Reasoning, nonmonotonicity and learning in connectionist networks that capture propositional knowledge
Pinkas, G. (1995) · Artificial Intelligence · doi:10.1016/0004-3702(94)00032-v · Cited by 128
Implicit Niching in a Learning Classifier System: Nature's Way
Horn, J., Goldberg, D. E., & Deb, K. (1994) · Evolutionary Computation · doi:10.1162/evco.1994.2.1.37 · Cited by 127
Learning monotone nonlinear models using the Choquet integral
Tehrani, A. F., Cheng, W., Dembczyński, K., & Hüllermeier, E. (2012) · Machine Learning · doi:10.1007/s10994-012-5318-3 · Cited by 126
Constant depth circuits, Fourier transform, and learnability
Linial, N., Mansour, Y., & Nisan, N. (1989) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63537 · Cited by 126
Noisy Monte Carlo: convergence of Markov chains with approximate transition kernels
Alquier, P., Friel, N., Everitt, R. G., & Boland, A. (2014) · Statistics and Computing · doi:10.1007/s11222-014-9521-x · Cited by 125
On the Fourier spectrum of monotone functions
Bshouty, N. H., & Tamon, C. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225125 · Cited by 125
Boosting textual compression in optimal linear time
Ferragina, P., Giancarlo, R., Manzini, G., & Sciortino, M. (2005) · Journal of the ACM · doi:10.1145/1082036.1082043 · Cited by 125
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (Extended Abstract)
Diakonikolas, I., Kane, D. M., & Stewart, A. (2017) · eScholarship (California Digital Library) · doi:10.1109/focs.2017.16 · Cited by 124
Machine learning and deep learning for sentiment analysis across languages: A survey
Mercha, E. M., & Benbrahim, H. (2023) · Neurocomputing · doi:10.1016/j.neucom.2023.02.015 · Cited by 123
An algorithm based on counterfactuals for concept learning in the Semantic Web
Iannone, L., Palmisano, I., & Fanizzi, N. (2007) · Applied Intelligence · doi:10.1007/s10489-006-0011-5 · Cited by 122
Virtual Occupancy Sensing: Using Smart Meters to Indicate Your Presence
Jin, M., Jia, R., & Spanos, C. J. (2017) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2017.2684806 · Cited by 122
The Ethics of Algorithms: Key Problems and Solutions
Tsamados, A., Aggarwal, N., Cowls, J., Morley, J., Roberts, H., Taddeo, M., & Floridi, L. (2021) · Philosophical Studies Series · doi:10.1007/978-3-030-81907-1_8 · Cited by 121
Model Generation by Moderated Regular Extrapolation
Hagerer, A., Hungar, H., Niese, O., & Steffen, B. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45923-5_6 · Cited by 121
Learning functions represented as multiplicity automata
Beimel, A., Bergadano, F., Bshouty, N. H., Kushilevitz, E., & Varricchio, S. (2000) · Journal of the ACM · doi:10.1145/337244.337257 · Cited by 121
Artificial Intelligence and Advanced Materials
López, C. (2022) · Advanced Materials · doi:10.1002/adma.202208683 · Cited by 123
Teachability in computational learning
Shinohara, A., & Miyano, S. (1991) · New Generation Computing · doi:10.1007/bf03037091 · Cited by 120
Chemoinformatics as a Theoretical Chemistry Discipline
Varnek, A. A., & Baskin, I. I. (2011) · Molecular Informatics · doi:10.1002/minf.201000100 · Cited by 127
Equivalences and Separations Between Quantum and Classical Learnability
Servedio, R. A., & Gortler, S. J. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539704412910 · Cited by 126
A discriminative model for semi-supervised learning
Balcan, M.-F., & Blum, A. L. (2010) · Journal of the ACM · doi:10.1145/1706591.1706599 · Cited by 118
Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks
Grubbs, P., Lacharité, M.-S., Minaud, B., & Paterson, K. G. (2019) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2019.00030 · Cited by 118
Attribute-value learning versus inductive logic programming: The missing links
Raedt, L. D. (1998) · Lecture notes in computer science · doi:10.1007/bfb0027304 · Cited by 119
A Survey on Blocking Technology of Entity Resolution
Li, B., Liu, Y., Zhang, A.-M., Wang, W.-H., & Wan, S. (2020) · Journal of Computer Science and Technology · doi:10.1007/s11390-020-0350-4 · Cited by 116
Deep learning with support vector data description
Kim, S., Choi, Y.-H., & Lee, M. (2015) · Neurocomputing · doi:10.1016/j.neucom.2014.09.086 · Cited by 116
Learning to Learn, from Transfer Learning to Domain Adaptation: A Unifying Perspective
Patricia, N., & Barbara Caputo, B. (2014) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2014.187 · Cited by 121
Fuzzy lattice reasoning (FLR) classifier and its application for ambient ozone estimation
Kaburlasos, V. G., Athanasiadis, I. N., & Mitkas, P. A. (2006) · International Journal of Approximate Reasoning · doi:10.1016/j.ijar.2006.08.001 · Cited by 115
Recent Results on Boolean Concept Learning
Kearns, M. J., Li, M., Pitt, L., & Valiant, L. G. (1987) · Elsevier eBooks · doi:10.1016/b978-0-934613-41-5.50037-4 · Cited by 115
Self-citation
Statistical Learning Theory and ELM for Big Social Data Analysis
Oneto, L., Bisio, F., Cambria, E., & Anguita, D. (2016) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2016.2572540 · Cited by 116
Zero-stimulation for parameter setting
Freidin, R., & Quicoli, A. C. (1989) · Behavioral and Brain Sciences · doi:10.1017/s0140525x00048937 · Cited by 114
PAC-learnability of determinate logic programs
Džeroski, S., Muggleton, S., & Russell, S. (1992) · Conference on Learning Theory · doi:10.1145/130385.130399 · Cited by 114
Beyond the Turing Test
Hernández‐Orallo, J. (2000) · Journal of Logic Language and Information · doi:10.1023/a:1008367325700 · Cited by 113
Improving a Network Generalization Ability by Selecting Examples
Kinzel, W., & Ruján, P. (1990) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/13/5/016 · Cited by 113
What Artificial Neural Networks Can Tell Us about Human Language Acquisition
Warstadt, A., & Bowman, S. R. (2022) · Algebraic Structures in Natural Language · doi:10.1201/9781003205388-2 · Cited by 111
Reduction from Cost-Sensitive Ordinal Ranking to Weighted Binary Classification
Lin, H.-T., & Li, L. (2012) · Neural Computation · doi:10.1162/neco_a_00265 · Cited by 111
Theoretical Views of Boosting
Schapire, R. E. (1999) · Lecture notes in computer science · doi:10.1007/3-540-49097-3_1 · Cited by 111
Exact learning via the Monotone theory
Bshouty, N. H. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366857 · Cited by 111
Learning nonsingular phylogenies and hidden Markov models
Mossel, E., & Roch, S. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060645 · Cited by 110

Authors: Valiant, L. G.
Affiliations: Harvard University (US)
Corresponding author: Valiant, L. G.
Venue: Communications of the ACM
Publisher: Association for Computing Machinery (ACM)
Published: 1984-11-05
Volume: 27
Issue: 11
Pages: 1134-1142
ISSN: 0001-0782 (ISSN-L)
1557-7317
DOI: 10.1145/1968.1972
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
Licence: www.acm.org/publications/policies/copyright_policy#Background (vor)
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

A theory of the learnable

Abstract

Overview

Integrity signals

Verification

Claims the paper makes

Claims other papers make about this one

Self-check

Citations

Cites

Cited by

Related

Metadata

Record

About these checks