{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:34:13Z","timestamp":1794357253912,"version":"4.9.0"},"publisher-location":"Boston, MA","reference-count":17,"publisher":"Springer US","isbn-type":[{"value":"9780387307701","type":"print"},{"value":"9780387301624","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_177","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T14:38:04Z","timestamp":1214491084000},"page":"385-387","source":"Crossref","is-referenced-by-count":3,"title":["Hardness of Proper Learning"],"prefix":"10.1007","author":[{"given":"Vitaly","family":"Feldman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"177_CR1_177","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1109\/FOCS.2004.36","volume-title":"FOCS '04 Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)","author":"M. Alekhnovich","year":"2004","unstructured":"Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A., Pitassi, T.: Learnability and automizability. In: Proceeding of FOCS, pp. 621\u2013630 (2004)"},{"key":"177_CR2_177","unstructured":"Ben-David, S., Eiron, N., Long, P. M.: On the difficulty of approximately maximizing agreements. In: Proceedings of COLT, pp. 266\u2013274 (2000)"},{"issue":"1","key":"177_CR3_177","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0893-6080(05)80010-3","volume":"5","author":"A.L. Blum","year":"1992","unstructured":"Blum, A.L., Rivest, R.L.: Training a 3-node neural network is NP-complete. Neural Netw. 5(1), 117\u2013127 (1992)","journal-title":"Neural Netw."},{"issue":"4","key":"177_CR4_177","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.: Learnability and the Vapnik-Chervonenkis dimension. J.\u00a0ACM 36(4), 929\u2013965 (1989)","journal-title":"J. ACM"},{"issue":"1","key":"177_CR5_177","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/inco.1995.1164","volume":"123","author":"N. Bshouty","year":"1995","unstructured":"Bshouty, N.: Exact learning via the monotone theory. Inf. Comput. 123(1), 146\u2013153 (1995)","journal-title":"Inf. Comput."},{"key":"177_CR6_177","doi-asserted-by":"crossref","unstructured":"Feldman, V.: Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries. In: Proceedings of STOC, pp. 363\u2013372 (2006)","DOI":"10.1145\/1132516.1132569"},{"key":"177_CR7_177","doi-asserted-by":"crossref","unstructured":"Feldman, V.: Optimal hardness results for maximizing agreements with monomials. In: Proceedings of Conference on Computational Complexity (CCC), pp. 226\u2013236 (2006)","DOI":"10.1109\/CCC.2006.31"},{"key":"177_CR8_177","unstructured":"Garey, M., Johnson, D.S.: Computers and Intractability. W. H. Freeman, San Francisco (1979)"},{"key":"177_CR9_177","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Raghavendra, P.: Hardness of Learning Halfspaces with Noise. In: Proceedings of FOCS, pp. 543\u2013552 (2006)","DOI":"10.1109\/FOCS.2006.33"},{"key":"177_CR10_177","doi-asserted-by":"crossref","unstructured":"Hancock, T., Jiang, T., Li, M., Tromp, J.: Lower bounds on learning decision lists and trees. In: 12th Annual Symposium on Theoretical Aspects of Computer Science, pp. 527\u2013538 (1995)","DOI":"10.1007\/3-540-59042-0_102"},{"issue":"1","key":"177_CR11_177","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","volume":"100","author":"D. Haussler","year":"1992","unstructured":"Haussler, D.: Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput. 100(1), 78\u2013150 (1992)","journal-title":"Inf. Comput."},{"key":"177_CR12_177","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J. Jackson","year":"1997","unstructured":"Jackson, J.: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. J.\u00a0Comput. Syst. Sci. 55, 414\u2013440 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2\u20133","key":"177_CR13_177","first-page":"115","volume":"17","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Schapire, R., Sellie, L.: Toward efficient agnostic learning. Mach. Learn. 17(2\u20133), 115\u2013141 (1994)","journal-title":"Mach. Learn."},{"issue":"1","key":"177_CR14_177","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Valiant, L.: Cryptographic limitations on learning boolean formulae and finite automata. J.\u00a0ACM 41(1), 67\u201395 (1994)","journal-title":"J. ACM"},{"key":"177_CR15_177","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An introduction to computational learning theory","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Vazirani, U.: An introduction to computational learning theory. MIT Press, Cambridge, MA (1994)"},{"issue":"4","key":"177_CR16_177","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L., Valiant, L.: Computational limitations on learning from examples. J. ACM 35(4), 965\u2013984 (1988)","journal-title":"J. ACM"},{"issue":"11","key":"177_CR17_177","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"Valiant, L.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_177","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T16:32:51Z","timestamp":1738254771000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_177"}},"subtitle":["1988; Pitt, Valiant"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_177","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2008]]}}}