{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T11:06:33Z","timestamp":1786100793951,"version":"3.56.0"},"reference-count":29,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1989,9,1]],"date-time":"1989-09-01T00:00:00Z","timestamp":620611200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8720,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[1989,9]]},"DOI":"10.1016\/0890-5401(89)90002-3","type":"journal-article","created":{"date-parts":[[2004,12,1]],"date-time":"2004-12-01T19:24:20Z","timestamp":1101929060000},"page":"247-261","source":"Crossref","is-referenced-by-count":224,"title":["A general lower bound on the number of examples needed for learning"],"prefix":"10.1016","volume":"82","author":[{"given":"Andrzej","family":"Ehrenfeucht","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Haussler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Kearns","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie","family":"Valiant","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"No. 4","key":"10.1016\/0890-5401(89)90002-3_bib1","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF00116828","article-title":"Identifying kCNF formulas from noisy examples","volume":"2","author":"Angluin","year":"1988","journal-title":"Mach. Learning"},{"key":"10.1016\/0890-5401(89)90002-3_bib2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","article-title":"Fast probabilistic algorithms for Hamiltonian circuits and matchings","volume":"18","author":"Angluin","year":"1979","journal-title":"J. Comput. System Sci."},{"issue":"No. 1","key":"10.1016\/0890-5401(89)90002-3_bib3","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1162\/neco.1989.1.1.151","article-title":"What size net gives valid generalization?","volume":"1","author":"Baum","year":"1989","journal-title":"Neural Computation"},{"key":"10.1016\/0890-5401(89)90002-3_bib4","series-title":"First Workshop on Computational Learning Theory","article-title":"Learnability by fixed distributions","author":"Benedek","year":"1988"},{"key":"10.1016\/0890-5401(89)90002-3_bib5","series-title":"18th ACM Symposium on the Theory of Computing","first-page":"273","article-title":"Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension","author":"Blumer","year":"1986"},{"key":"10.1016\/0890-5401(89)90002-3_bib6","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","article-title":"Occam's razor","volume":"24","author":"Blumer","year":"1987","journal-title":"Inform. Process. Lett."},{"issue":"No. 4","key":"10.1016\/0890-5401(89)90002-3_bib7","doi-asserted-by":"crossref","DOI":"10.1145\/76359.76371","article-title":"Learnability and the Vapnik-Chervonenkis Dimension","volume":"36","author":"Blumer","year":"1989","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0890-5401(89)90002-3_bib8","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations","volume":"23","author":"Chernoff","year":"1952","journal-title":"Ann. Math. Stat."},{"key":"10.1016\/0890-5401(89)90002-3_bib9","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0004-3702(88)90002-1","article-title":"Quantifying inductive bias: AI learning algorithms and Valiant's model","volume":"36","author":"Haussler","year":"1988","journal-title":"Artif. Intell."},{"key":"10.1016\/0890-5401(89)90002-3_bib10","series-title":"29th IEEE Symposium on Foundations of Computer Science","first-page":"100","article-title":"Predicting {0, 1}-functions on randomly drawn points","author":"Haussler","year":"1988"},{"key":"10.1016\/0890-5401(89)90002-3_bib11","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","article-title":"Epsilon-nets and simplex range queries","volume":"2","author":"Haussler","year":"1987","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/0890-5401(89)90002-3_bib12","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","article-title":"A new polynomial-time algorithm for linear programming","volume":"4","author":"Karmarkar","year":"1984","journal-title":"Combinatorica"},{"key":"10.1016\/0890-5401(89)90002-3_bib13","article-title":"The computational complexity of machine learning","author":"Kearns","year":"1989","journal-title":"Harvard University doctoral dissertation"},{"key":"10.1016\/0890-5401(89)90002-3_bib14","series-title":"20th ACM Symposium on the Theory of Computing","first-page":"267","article-title":"Learning in the presence of malicious errors","author":"Kearns","year":"1988"},{"key":"10.1016\/0890-5401(89)90002-3_bib15","series-title":"19th ACM Symposium on the Theory of Computing","first-page":"285","article-title":"On the learnability of Boolean formulae","author":"Kearns","year":"1987"},{"key":"10.1016\/0890-5401(89)90002-3_bib16","series-title":"21st ACM Symposium on the Theory of Computing","first-page":"433","article-title":"Cryptographic limitations on learning Boolean formulae and finite automata","author":"Kearns","year":"1989"},{"key":"10.1016\/0890-5401(89)90002-3_bib17","first-page":"191","article-title":"A polynomial algorithm for linear programming","volume":"244:S","author":"Khachiyan","year":"1979","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"No. 4","key":"10.1016\/0890-5401(89)90002-3_bib18","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BF00116827","article-title":"Learning quickly when irrelevant attributes abound: A new linear threshold algorithm","volume":"2","author":"Littlestone","year":"1988","journal-title":"Mach. Learning"},{"key":"10.1016\/0890-5401(89)90002-3_bib19","series-title":"First Workshop on Computational Learning Theory","article-title":"Results on learnability and the Vapnik-Chervonenkis dimension","author":"Linial","year":"1988"},{"key":"10.1016\/0890-5401(89)90002-3_bib20","series-title":"19th ACM Symposium on the Theory of Computing","first-page":"296","article-title":"On learning Boolean functions","author":"Natarajan","year":"1987"},{"issue":"No. 4","key":"10.1016\/0890-5401(89)90002-3_bib21","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","article-title":"Computational Limitations on Learning from Examples","volume":"35","author":"Pitt","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"issue":"No. 3","key":"10.1016\/0890-5401(89)90002-3_bib22","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF00058680","article-title":"Learning decision lists","volume":"2","author":"Rivest","year":"1987","journal-title":"Mach. Learning"},{"key":"10.1016\/0890-5401(89)90002-3_bib23","series-title":"First Workshop on Computational Learning Theory","article-title":"Non-learnable classes of Boolean formulae that are closed under variable permutation","author":"Shvayster","year":"1988"},{"issue":"No. 11","key":"10.1016\/0890-5401(89)90002-3_bib24","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1984","journal-title":"Comm. ACM"},{"key":"10.1016\/0890-5401(89)90002-3_bib25","series-title":"Proceedings, 9th IJCAI","first-page":"560","article-title":"Learning disjunctions of conjunctions","author":"Valiant","year":"1985"},{"key":"10.1016\/0890-5401(89)90002-3_bib26","author":"Vapnik","year":"1982"},{"issue":"No. 2","key":"10.1016\/0890-5401(89)90002-3_bib27","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","article-title":"On the uniform convergence of relative frequencies of events to their probabilities","volume":"16","author":"Vapnik","year":"1971","journal-title":"Theory Probab. Appl"},{"key":"10.1016\/0890-5401(89)90002-3_bib28","series-title":"First Workshop on Computational Learning Theory","article-title":"Learning in parallel","author":"Vitter","year":"1988"},{"key":"10.1016\/0890-5401(89)90002-3_bib29","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0012-365X(81)90274-0","article-title":"Some special Vapnik-Chervonenkis classes","volume":"33","author":"Wenocur","year":"1981","journal-title":"Discrete Math."}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540189900023?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540189900023?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,1]],"date-time":"2019-02-01T13:26:48Z","timestamp":1549027608000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0890540189900023"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,9]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1989,9]]}},"alternative-id":["0890540189900023"],"URL":"https:\/\/doi.org\/10.1016\/0890-5401(89)90002-3","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[1989,9]]}}}