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 701–800 of 1,004

On the Convergence of Tsetlin Machines for the XOR Operator
Jiao, L., Zhang, X., Granmo, O., & Abeyrathna, K. D. (2022) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2022.3203150 · Cited by 37
An Improved Federated Learning Algorithm for Privacy Preserving in Cybertwin-Driven 6G System
Yang, M., Wang, X., Qian, H. L., Zhu, Y., Zhu, H., Guizani, M., & Chang, V. I. C. (2022) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2022.3149516 · Cited by 37
The Worst of Both Worlds: A Comparative Analysis of Errors in Learning from Data in Psychology and Machine Learning
Hullman, J. R., Kapoor, S., Nanayakkara, P., Gelman, A., & Narayanan, A. (2022) · Proceedings of the AAAI/ACM Conference on AI Ethics and Society · doi:10.1145/3514094.3534196 · Cited by 48
Three-step neural network approach for predicting monsoon flood preparedness and adaptation: Application in urban communities of Lahore, Pakistan
Rana, I. A., Lodhi, R. H., Zia, A., Jamshed, A., & Nawaz, A. (2022) · Urban Climate · doi:10.1016/j.uclim.2022.101266 · Cited by 37
On multi-class problems and discretization in inductive logic programming
Laer, W. V., Raedt, L. D., & Džeroski, S. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63614-5_27 · Cited by 37
Margin-based active learning for structured predictions
Small, K., & Roth, D. (2010) · International Journal of Machine Learning and Cybernetics · doi:10.1007/s13042-010-0003-y · Cited by 37
A DNA-based memory with in vitro learning and associative recall
Chen, J., Deaton, R. J., & Wang, Y. (2005) · Natural Computing · doi:10.1007/s11047-004-4002-3 · Cited by 37
A complete characterization of statistical query learning with applications to evolvability
Feldman, V. (2012) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2011.12.024 · Cited by 37
A probabilistic framework for memory-based reasoning
Kasif, S., Salzberg, S. L., Waltz, D. L., Rachlin, J., & Aha, D. W. (1998) · Artificial Intelligence · doi:10.1016/s0004-3702(98)00046-0 · Cited by 37
Learning under persistent drift
Freund, Y., & Mansour, Y. (1997) · Lecture notes in computer science · doi:10.1007/3-540-62685-9_10 · Cited by 37
Encouraging Experimental Results on Learning CNF
Mooney, R. J. (1995) · Machine Learning · doi:10.1007/bf00994661 · Cited by 37
Simple learning algorithms using divide and conquer
Bshouty, N. H. (1996) · Computational Complexity · doi:10.1007/bf01262930 · Cited by 37
Towards a mathematical theory of machine discovery from facts
Mukouchi, Y., & Arikawa, S. (1995) · Theoretical Computer Science · doi:10.1016/0304-3975(95)91135-d · Cited by 37
Learning Sums of Independent Integer Random Variables
Daskalakis, C., Diakonikolas, I., O’Donnell, R., Servedio, R. A., & Tan, L.-Y. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.31 · Cited by 36
An Equivalence Between Private Classification and Online Prediction
Bun, M., Livni, R., & Moran, S. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00044 · Cited by 47
On the impact of forgetting on learning machines
Freivalds, R., Kinber, E. B., & Smith, C. H. (1995) · Journal of the ACM · doi:10.1145/227683.227685 · Cited by 36
Generalized Linear Models
Wüthrich, M. V., & Merz, M. (2022) · Springer Actuarial · doi:10.1007/978-3-031-12409-9_5 · Cited by 36
Measuring teachability using variants of the teaching dimension
Balbach, F. J. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.02.025 · Cited by 36
Four types of noise in data for PAC learning
Sloan, R. H. (1995) · Information Processing Letters · doi:10.1016/0020-0190(95)00016-6 · Cited by 36
Queries Revisited
Angluin, D. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45583-3_3 · Cited by 36
Classification by Feature Partitioning
Güvenir, H. A., & Şirin, İ. (1996) · Machine Learning · doi:10.1007/bf00116899 · Cited by 36
Agnostic Learning of Geometric Patterns
Goldman, S. A., Kwek, S. S., & Scott, S. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1723 · Cited by 36
General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
Aslam, J. A., & Decatur, S. E. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366859 · Cited by 36
Interactive reconstruction via geometric probing
Skiena, S. (1992) · Proceedings of the IEEE · doi:10.1109/5.163406 · Cited by 36
Constructive learning techniques for designing neural network systems
Campbell, C. (1998) · Neural network systems techniques and applications · doi:10.1016/s1874-5946(98)80005-9 · Cited by 36
Toward Machine Wald
Owhadi, H., & Scovel, C. (2017) · Springer eBooks · doi:10.1007/978-3-319-12385-1_3 · Cited by 35
Mental models of Boolean concepts
Goodwin, G. P., & Johnson-Laird, P. N. (2011) · Cognitive Psychology · doi:10.1016/j.cogpsych.2011.04.001 · Cited by 35
Vote Elicitation with Probabilistic Preference Models: Empirical Estimation and Cost Tradeoffs
Lu, T., & Boutilier, C. E. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-24873-3_11 · Cited by 35
Understanding generalization error of SGD in nonconvex optimization
Zhou, Y., Liang, Y., & Zhang, H. (2021) · Machine Learning · doi:10.1007/s10994-021-06056-w · Cited by 48
A Scheme for Continuous Input to the Tsetlin Machine with Applications to Forecasting Disease Outbreaks
Abeyrathna, K. D., Granmo, O., Zhang, X., & Goodwin, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-22999-3_49 · Cited by 35
Pseudo-dimension of quantum circuits
Caro, M. C., & Datta, I. (2020) · Quantum Machine Intelligence · doi:10.1007/s42484-020-00027-5 · Cited by 35
Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
Caro, M. C. (2024) · ACM Transactions on Quantum Computing · doi:10.1145/3670418 · Cited by 61
A Short Tour of the Predictive Modeling Process
Kühn, M., & Johnson, K. (2013) · Springer eBooks · doi:10.1007/978-1-4614-6849-3_2 · Cited by 36
Learning of Boolean Functions Using Support Vector Machines
Sadohara, K. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45583-3_10 · Cited by 35
Efficient learning algorithms yield circuit lower bounds
Fortnow, L., & Klivans, A. R. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2008.07.006 · Cited by 39
The geometry of quantum learning
Hunziker, M., Meyer, D., Park, J., Pommersheim, J., & Rothstein, M. J. (2009) · Quantum Information Processing · doi:10.1007/s11128-009-0129-6 · Cited by 35
Uncertainty-Driven Black-Box Test Data Generation
Walkinshaw, N., & Fraser, G. (2017) · IEEE International Conference on Software Testing, Verification and Validation (ICST) · doi:10.1109/icst.2017.30 · Cited by 35
Feature Selection
Theodoridis, S., & Koutroumbas, K. (2009) · Elsevier eBooks · doi:10.1016/b978-1-59749-272-0.50007-4 · Cited by 35
mARGOt: A Dynamic Autotuning Framework for Self-Aware Approximate Computing
Gadioli, D., Vitali, E., Palermo, G., & Silvano, C. (2018) · IEEE Transactions on Computers · doi:10.1109/tc.2018.2883597 · Cited by 35
Sample complexity for learning recurrent perceptron mappings
Dasgupta, B., & Sontag, E. D. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.532888 · Cited by 35
Complexity theory of neural networks and classification problems
Cybenko, G. V. (1990) · Lecture notes in computer science · doi:10.1007/3-540-52255-7_25 · Cited by 35
More efficient PAC-learning of DNF with membership queries under the uniform distribution
Bshouty, N. H., Jackson, J. C., & Tamon, C. (1999) · Conference on Learning Theory · doi:10.1145/307400.307472 · Cited by 35
Exact identification of circuits using fixed points of amplification functions
Goldman, S. A., Kearns, M. J., & Schapire, R. E. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89538 · Cited by 35
CSL: a cost-sensitive learning system for sensing and grasping objects
Tan, M. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1990.126097 · Cited by 35
Learning dynamical systems in a stationary environment
Campi, M. C., & Kumar, P. R. (1998) · Systems & Control Letters · doi:10.1016/s0167-6911(98)00005-x · Cited by 35
A Statistical Approach to Learning and Generalization in Layered Neural Networks
Levin, E., Tishby, N., & Solla, S. A. (1989) · Elsevier eBooks · doi:10.1016/b978-0-08-094829-4.50020-9 · Cited by 35
Learning conjunctions of Horn clauses
Angluin, D., Frazier, M., & Pitt, L. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89537 · Cited by 35
Read-thrice DNF is hard to learn with membership and equivalence queries
Aizenstein, H. J., Hellerstein, L., & Pitt, L. (1992) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267799 · Cited by 35
Explicitly biased generalization
Gordon, D. F., & Perlis, D. R. (1989) · Computational Intelligence · doi:10.1111/j.1467-8640.1989.tb00317.x · Cited by 35
Noise-Tolerant Occam Algorithms and Their Applications to Learning Decision Trees
Sakakibara, Y. (1993) · Machine Learning · doi:10.1023/a:1022679002094 · Cited by 34
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
Feldman, V., & Vondrák, J. (2016) · SIAM Journal on Computing · doi:10.1137/140958207 · Cited by 34
The Unbounded-Error Communication Complexity of Symmetric Functions
Sherstov, A. A. (2008) · COMBINATORICA · doi:10.1007/s00493-011-2580-0 · Cited by 34
Sample-efficient strategies for learning in the presence of noise
Cesa‐Bianchi, N., Dichterman, E., Fischer, P., Shamir, E., & Simon, H. U. (1999) · Journal of the ACM · doi:10.1145/324133.324221 · Cited by 34
Halfspace Matrices
Sherstov, A. A. (2007) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2007.11 · Cited by 34
Optimization approaches to Supervised Classification
Silva, A. P. D. (2017) · European Journal of Operational Research · doi:10.1016/j.ejor.2017.02.020 · Cited by 35
Machine learning for information extraction
Neri, F., & Saitta, L. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63438-x_9 · Cited by 34
Evolution and generalization of a single neurone:
Raudys, Š. (1998) · Neural Networks · doi:10.1016/s0893-6080(97)00136-6 · Cited by 34
Geometric learning algorithms
Omohundro, S. M. (1990) · Physica D Nonlinear Phenomena · doi:10.1016/0167-2789(90)90085-4 · Cited by 34
On learning from queries and counterexamples in the presence of noise
Sakakibara, Y. (1991) · Information Processing Letters · doi:10.1016/0020-0190(91)90220-c · Cited by 34
Abductive Explanation-Based Learning: A Solution to the Multiple Inconsistent Explanation Problem
Cohen, W. W. (1992) · Machine Learning · doi:10.1007/bf00992863 · Cited by 34
PAC learning with irrelevant attributes
Dhagat, A., & Hellerstein, L. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365704 · Cited by 34
How to Upgrade Propositional Learners to First Order Logic: A Case Study
Laer, W. V., & Raedt, L. D. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44673-7_5 · Cited by 34
Classic Learning
Frazier, M., & Pitt, L. (1996) · Machine Learning · doi:10.1007/bf00114009 · Cited by 34
Analytical Survey of Learning with Low-Resource Data: From Analysis to Investigation
Cao, X., Xu, M., Yu, X., Yao, J., Ye, W., Huang, S.-J., Zhang, M.-L., Tsang, I. W.-H., Ong, Y.-S., Kwok, J. T.-Y., et al. (2025) · ACM Computing Surveys · doi:10.1145/3773075 · Cited by 37
Learning minimal abstractions
Liang, P., Tripp, O., & Naik, M. (2011) · ACM SIGPLAN Notices · doi:10.1145/1925844.1926391 · Cited by 33
Learning-Based Testing of Cyber-Physical Systems-of-Systems: A Platooning Study
Meinke, K. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-66583-2_9 · Cited by 33
Culture and computation: Steps to a Probably Approximately Correct theory of culture
Foster, J. G. (2018) · Poetics · doi:10.1016/j.poetic.2018.04.007 · Cited by 33
The usefulness of socio-demographic variables in predicting purchase decisions: Evidence from machine learning procedures
Islam, T., Meade, N., Carson, R. T., Louviere, J. J., & Wang, J. (2022) · Journal of Business Research · doi:10.1016/j.jbusres.2022.07.004 · Cited by 38
Minimization, Learning, and Conformance Testing of Boolean Programs
Kumar, V., Madhusudan, P., & Viswanathan, M. (2006) · Lecture notes in computer science · doi:10.1007/11817949_14 · Cited by 33
Remedies for Severe Class Imbalance
Kühn, M., & Johnson, K. (2013) · Springer eBooks · doi:10.1007/978-1-4614-6849-3_16 · Cited by 35
The Synthesis of Language Learners
Baliga, G. R., Case, J., & Jain, S. K. (1999) · Information and Computation · doi:10.1006/inco.1998.2782 · Cited by 33
The Value of Field Experiments
Li, J. Q., Rusmevichientong, P., Simester, D. I., Tsitsiklis, J. N., & Zoumpoulis, S. I. (2015) · Management Science · doi:10.1287/mnsc.2014.2066 · Cited by 33
Evolutionary game dynamics in populations with different learners
Chatterjee, K., Damien Zufferey, A., & Nowak, M. A. (2012) · Journal of Theoretical Biology · doi:10.1016/j.jtbi.2012.02.021 · Cited by 33
Knowledge as a service and knowledge breaching
Xu, S., & Zhang, W. (2005) · IEEE International Conference on Services Computing · doi:10.1109/scc.2005.60 · Cited by 33
A Semi-supervised Approach for Reject Inference in Credit Scoring Using SVMs
Maldonado, S., & Paredes, G. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14400-4_43 · Cited by 33
Principled network reliability approximation: A counting-based approach
Paredes, R., Dueñas‐Osorio, L., Meel, K. S., & Vardi, M. Y. (2019) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2019.04.025 · Cited by 33
Bloom Filters in Adversarial Environments
Naor, M., & Yogev, E. (2019) · ACM Transactions on Algorithms · doi:10.1145/3306193 · Cited by 33
Finding Essential Attributes from Binary Data
Boros, E., Horiyama, T., Ibaraki, T., Makino, K., & Yagiura, M. (2003) · Annals of Mathematics and Artificial Intelligence · doi:10.1023/a:1024653703689 · Cited by 33
Primate Social Intelligence
Worden, R. (1996) · Cognitive Science · doi:10.1207/s15516709cog2004_4 · Cited by 33
Information theory, complexity and neural networks
Abu‐Mostafa, Y. S. (1989) · IEEE Communications Magazine · doi:10.1109/35.41397 · Cited by 33
A role of total margin in support vector machines
Yoon, M., Yun, Y., & Nakayama, H. (2004) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2003.1223723 · Cited by 33
Classification by polynomial surfaces
Anthony, M. (1995) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)00008-2 · Cited by 33
On the Learnability of Disjunctive Normal Form Formulas
Aizenstein, H. J., & Pitt, L. (1995) · Machine Learning · doi:10.1007/bf00996269 · Cited by 33
Combining Data Envelopment Analysis and Machine Learning
Guerrero, N. M., Aparicio, J., & Valero-Carreras, D. (2022) · Mathematics · doi:10.3390/math10060909 · Cited by 32
On the complexity of trial and error
Bei, X., Chen, N., & Zhang, S. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488613 · Cited by 32
Probably Approximately Symmetric: Fast Rigid Symmetry Detection With Global Guarantees
Korman, S., Litman, R., Avidan, S., & Bronstein, A. M. (2014) · Computer Graphics Forum · doi:10.1111/cgf.12454 · Cited by 32
Construction of class regions by a randomized algorithm: a randomized subclass method
Kudo, M., Yanagi, S., & Shimbo, M. (1996) · Pattern Recognition · doi:10.1016/0031-3203(95)00107-7 · Cited by 32
Constructing a generalizer superior to NETtalk via a mathematical theory of generalization
Wolpert, D. H. (1990) · Neural Networks · doi:10.1016/0893-6080(90)90027-i · Cited by 33
On the Complexity of Learning Minimum Time-Bounded Turing Machines
Ko, K. (1991) · SIAM Journal on Computing · doi:10.1137/0220059 · Cited by 31
Information extraction from structured documents using k-testable tree automaton inference
Kosala, R., Blockeel, H., Bruynooghe, M., & den Bussche, J. V. (2005) · Data & Knowledge Engineering · doi:10.1016/j.datak.2005.05.002 · Cited by 31
TeLEx: Passive STL Learning Using Only Positive Examples
Jha, S., Tiwari, A., Seshia, S. A., Sahai, T., & Shankar, N. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-67531-2_13 · Cited by 31
Synergy of physics-based reasoning and machine learning in biomedical applications: towards unlimited deep learning with limited data
Gavrishchaka, V., Senyukova, O., & Koepke, M. E. (2019) · Advances in Physics X · doi:10.1080/23746149.2019.1582361 · Cited by 32
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
Sherstov, A. A. (2010) · COMBINATORICA · doi:10.1007/s00493-013-2759-7 · Cited by 31
Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions
Haitner, I., Reingold, O., & Vadhan, S. (2013) · SIAM Journal on Computing · doi:10.1137/100814421 · Cited by 31
The Probably Approximately Correct (PAC) and Other Learning Models
Haussler, D. H., & Warmuth, M. K. (2007) · Springer eBooks · doi:10.1007/978-0-585-27366-2_9 · Cited by 31
On agnostic boosting and parity learning
Kalai, A. T., Mansour, Y., & Verbin, E. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374466 · Cited by 31
How to Upgrade Propositional Learners to First Order Logic: A Case Study
Laer, W. V., & Raedt, L. D. (2001) · Springer eBooks · doi:10.1007/978-3-662-04599-2_10 · Cited by 31
The relevance of relevance
Subramanian, D., Greiner, R., & Pearl, J. (1997) · Artificial Intelligence · doi:10.1016/s0004-3702(97)00075-1 · Cited by 31
An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
Pirnay, N., Ulitzsch, V. Q., Wilde, F., Eisert, J., & Seifert, J. (2024) · Science Advances · doi:10.1126/sciadv.adj5170 · Cited by 30
The learnability of unknown quantum measurements
Cheng, H., Hsieh, M.-H., & Yeh, P. (2016) · Quantum Information and Computation · doi:10.26421/qic16.7-8-4 · Cited by 40

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