{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T13:24:53Z","timestamp":1726406693631},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540566021"},{"type":"electronic","value":"9783540475972"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56602-3_150","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:19:48Z","timestamp":1330255188000},"page":"354-359","source":"Crossref","is-referenced-by-count":0,"title":["Can complexity theory benefit from Learning Theory?"],"prefix":"10.1007","author":[{"given":"Tibor","family":"Heged\u00fcs","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"27_CR1","unstructured":"D. Angluin, \u201dLearning k-term DNF Formulas Using Queries and Counterexamples\u201d, Technical Report, Yale University, YALE\/DCS\/RR-559, 1987."},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"D. Angluin, \u201dComputational Learning Theory: Survey and Selected Bibliography\u201d, in: Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, 1992, pp. 351\u2013369.","DOI":"10.1145\/129712.129746"},{"key":"27_CR3","volume-title":"Computational Learning Theory","author":"M. Anthony","year":"1992","unstructured":"M. Anthony and N. Biggs, Computational Learning Theory, Cambridge University Press, Cambridge, 1992."},{"key":"27_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979."},{"key":"27_CR5","unstructured":"T. Heged\u00fcs, \u201cComputational Limitations on PAC and On-Line Learning over the Boolean Domain: a Comparison\u201d, submitted for publication."},{"key":"27_CR6","unstructured":"T. Heged\u00fcs and N. Megiddo, \u201dOn the Geometric Separability of Boolean Functions\u201d, submitted for publication."},{"key":"27_CR7","first-page":"262","volume-title":"On the Complexity of Learning from Counterexamples","author":"W. Maass","year":"1989","unstructured":"W. Maass and Gy. Tur\u00e1n, \u201cOn the Complexity of Learning from Counterexamples\u201d, in: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Angeles, 1989, pp. 262\u2013267."},{"key":"27_CR8","unstructured":"W. Maass and Gy. Tur\u00e1n, \u201cAlgorithms and Lower Bounds for On-Line Learning of Geometrical Concepts\u201d, Report 316, IIG-Report Series, Graz University of Technology, 1991."},{"key":"27_CR9","unstructured":"W. Maass and Gy. Tur\u00e1n, \u201cHow Fast can a Threshold Gate Learn?\u201d Report 321, IIG-Report Series, Graz University of Technology, 1991."},{"key":"27_CR10","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, \u201dComputational Limitations on Learning from Examples\u201d, Journal of the ACM\n35 (1988) 965\u2013984.","journal-title":"Journal of the ACM"},{"key":"27_CR11","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"L. Valiant, \u201dA Theory of the Learnable\u201d, Communications of the ACM\n27 (1984) 1134\u20131142.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Machine Learning: ECML-93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56602-3_150.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T00:53:43Z","timestamp":1619571223000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56602-3_150"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540566021","9783540475972"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-56602-3_150","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}