{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:48:06Z","timestamp":1764841686272},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_102","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:59:56Z","timestamp":1330275596000},"page":"527-538","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Lower bounds on learning decision lists and trees"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Hancock","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Tromp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"46_CR1","unstructured":"Aditi Dhagat and Lisa Hellerstein. PAC learning with irrelevant attributes. To appear in Proc. 35rd IEEE Symp. Found. Comp. Sci., 1994."},{"key":"46_CR2","unstructured":"M. Anthony and N. Biggs. Computational Learning Theory. Cambridge University Press, 1992."},{"key":"46_CR3","unstructured":"R. Board and L. Pitt, On the necessity of Occam Algorithms. 1990 STOC, pp. 54\u201363."},{"key":"46_CR4","doi-asserted-by":"crossref","unstructured":"A. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. Proc. 33rd IEEE Symp. Found. Comp. Sci., 1992, 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"46_CR5","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, and A. Russel. Efficient probabilistically checkable proofs and applications to approximation. Proc. 25th ACM Symp. on Theory of Computing, 1993, 294\u2013304.","DOI":"10.1145\/167088.167174"},{"key":"46_CR6","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"35","author":"A. Blumer","year":"1989","unstructured":"A. Blumer and A. Ehrenfeucht and D. Haussler and M. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. Assoc. Comput. Mach., 35 (1989), 929\u2013965.","journal-title":"J. Assoc. Comput. Mach."},{"key":"46_CR7","volume-title":"Classification and Regression Trees","author":"L. Breiman","year":"1984","unstructured":"L. Breiman, J. Friedman, R. Olshen and C. Stone. Classification and Regression Trees. Wadsworth International Group, Belmont, CA (1984)."},{"key":"46_CR8","unstructured":"A. Ehrenfeucht and D. Haussler. Learning decision trees from random examples. COLT'88."},{"key":"46_CR9","volume-title":"Computers and Intractability","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson. Computers and Intractability. Freeman, New York, 1979."},{"issue":"2","key":"46_CR10","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0004-3702(88)90002-1","volume":"36","author":"D. Haussler","year":"1988","unstructured":"D. Haussler. Quantifying inductive bias: AI learning algorithms and Valiant's learning framework. Artificial Intelligence 36:2 (1988), 177\u2013222.","journal-title":"Artificial Intelligence"},{"issue":"1","key":"46_CR11","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0020-0190(76)90095-8","volume":"5","author":"L. Hyafil","year":"1976","unstructured":"L. Hyafil and R. Rivest. Constructing optimal decision trees is NP-complete. IPL, 5:1 (1976), 15\u201317.","journal-title":"IPL"},{"key":"46_CR12","doi-asserted-by":"crossref","unstructured":"M. Kearns, M. Li, L. Pitt, L. Valiant. On the learnability of Boolean functions. Proc. 19th STOC, 1987, New York, 285\u2013295.","DOI":"10.1145\/28395.28426"},{"key":"46_CR13","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Proc. 25th ACM Symp. on Theory of Computing, 1993, 286\u2013293.","DOI":"10.1145\/167088.167172"},{"key":"46_CR14","first-page":"319","volume":"3","author":"J. Mingers","year":"1989","unstructured":"J. Mingers. An empirical comparison of selection measures for decision-tree induction. Machine Learning. 3 (1989), 319\u2013342.","journal-title":"Machine Learning"},{"key":"46_CR15","first-page":"81","volume":"1","author":"J.R. Quinlan","year":"1986","unstructured":"J.R. Quinlan. Induction of decision trees. Machine Learning. 1 (1986), 81\u2013106.","journal-title":"Machine Learning"},{"key":"46_CR16","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0890-5401(89)90010-2","volume":"80","author":"J.R. Quinlan","year":"1989","unstructured":"J.R. Quinlan and R. Rivest. Inferring decision trees using the minimum description length principle. Inform. Computation, 80 (1989), 227\u2013248.","journal-title":"Inform. Computation"},{"key":"#cr-split#-46_CR17.1","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Extended abstract in Proc. 20th ACM Symp. on Theory of Computing. 1988, 229-234","DOI":"10.1145\/62212.62233"},{"key":"#cr-split#-46_CR17.2","doi-asserted-by":"crossref","unstructured":"full version in Journal of Computer and System Sciences 43, 1991, 425-440.","DOI":"10.1016\/0022-0000(91)90023-X"},{"issue":"4","key":"46_CR18","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"L. Pitt and L. Valiant. Computational limitations on learning from examples. Journal of the ACM, 35:4 (1988), 965\u2013984.","journal-title":"Journal of the ACM"},{"key":"46_CR19","first-page":"229","volume":"2","author":"R. Rivest","year":"1987","unstructured":"R. Rivest. Learning decision lists. Machine Learning, 2 (1987), 229\u2013246.","journal-title":"Machine Learning"},{"key":"46_CR20","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"L. Valiant. A theory of the learnable. Communications of the ACM. 27 (1984), 1134\u20131142.","journal-title":"Communications of the ACM."}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T00:13:24Z","timestamp":1578528804000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_102"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_102","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}