{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:23:22Z","timestamp":1778293402413,"version":"3.51.4"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1994,3,1]],"date-time":"1994-03-01T00:00:00Z","timestamp":762480000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1994,3,1]],"date-time":"1994-03-01T00:00:00Z","timestamp":762480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Machine Learning"],"published-print":{"date-parts":[[1994,3]]},"DOI":"10.1023\/a:1022653511837","type":"journal-article","created":{"date-parts":[[2003,4,4]],"date-time":"2003-04-04T16:55:36Z","timestamp":1049475336000},"page":"251-269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts"],"prefix":"10.1007","volume":"14","author":[{"given":"Wolfgang","family":"Maass","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"422441_CR1","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1023\/A:1022821128753","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D. (1988). Queries and concept learning. Machine Learning, 2, 319\u2013342.","journal-title":"Machine Learning"},{"key":"422441_CR2","unstructured":"Beals, R. (1990). Unpublished manuscript."},{"key":"422441_CR3","first-page":"9","volume-title":"Proceedings of the 1988 Workshop on Computational Learning Theory","author":"A. Blum","year":"1988","unstructured":"Blum, A., & Rivest, R.L. (1988). Training a 3-node neural network is NP-complete. Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 9\u201318). San Mateo, CA: Morgan Kaufmann."},{"key":"422441_CR4","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M.K. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36, 929\u2013965.","journal-title":"Journal of the ACM"},{"key":"422441_CR5","first-page":"337","volume-title":"Proceedings of the 4th Workshop on Computational Learning Theory 1991","author":"W. Bultman","year":"1991","unstructured":"Bultman, W., & Maass, W. (1991). Fast identification of geometric objects with membership queries. Proceedings of the 4th Workshop on Computational Learning Theory 1991 (pp. 337\u2013353). San Mateo, CA: Morgan Kaufmann."},{"key":"422441_CR6","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0890-5401(91)90042-Z","volume":"95","author":"D. Haussler","year":"1991","unstructured":"Haussler, D., Kearns, M., Littlestone, N., & Warmuth, M.K. (1991). Equivalence of models for polynomial learnability. Information and Computation, 95, 129\u2013161.","journal-title":"Information and Computation"},{"key":"422441_CR7","unstructured":"Haussler, D., Littlestone, N., & Warmuth, M.K. (1987). Expected mistake bounds for on-line learning algorithms. Unpublished manuscript."},{"key":"422441_CR8","first-page":"280","volume-title":"Proceedings of the 1st Workshop on Computational Learning Theory 1988","author":"D. Haussler","year":"1988","unstructured":"Haussler, D., Littlestone, N., & Warmuth, M.K. (1988). Predicting {0, 1}-functions on randomly drawn points. Proceedings of the 1st Workshop on Computational Learning Theory 1988 (pp. 280\u2013296). San Mateo, CA: Morgan Kaufmann."},{"key":"422441_CR9","doi-asserted-by":"crossref","unstructured":"Lippmann, R.P. (1987). An introduction to computing with neural nets. IEEE ASSP Magazine, 4\u201322.","DOI":"10.1109\/MASSP.1987.1165576"},{"key":"422441_CR10","doi-asserted-by":"crossref","unstructured":"Maass, W., & Tur\u00e1n, Gy. (1989). On the complexity of learning from counterexamples (extended abstract). Proceedings of the 30th IEEE FOCS 1989 (pp. 262\u2013267).","DOI":"10.1109\/SFCS.1989.63488"},{"key":"422441_CR11","doi-asserted-by":"crossref","unstructured":"Maass, W., & Tur\u00e1n, Gy. (1990). On the complexity of learning from counterexamples and membership queries (extended abstract). Proceedings of the 31st Annual IEEE FOCS (pp. 203\u2013210).","DOI":"10.1109\/FSCS.1990.89539"},{"key":"422441_CR12","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1023\/A:1022637031594","volume":"9","author":"W. Maass","year":"1992","unstructured":"Maass, W., & Tur\u00e1n, Gy. (1992). Lower bound methods and separation results for on-line learning models. Machine Learning, 9, 107\u2013145.","journal-title":"Machine Learning"},{"key":"422441_CR13","unstructured":"Maass, W., & Tur\u00e1n, Gy. (In press.) How fast can a threshold gate learn? In G. Drastal, S.J. Hanson, & R. Rivest (Eds.), Computational learning theory and natural learning systems: Constraints and prospects. Cambridge, MA: MIT Press."},{"key":"422441_CR14","volume-title":"Perceptrons: An introduction to computational geometry, expanded edition","author":"M. Minsky","year":"1988","unstructured":"Minsky, M., & Papert, S. (1988). Perceptrons: An introduction to computational geometry, expanded edition. Cambridge, MA: MIT Press."},{"key":"422441_CR15","volume-title":"Threshold logic and its applications","author":"S. Muroga","year":"1971","unstructured":"Muroga, S. (1971). Threshold logic and its applications. New York: Wiley."},{"key":"422441_CR16","volume-title":"Learning machines","author":"N.J. Nilsson","year":"1965","unstructured":"Nilsson, N.J. (1965). Learning machines. New York: McGraw-Hill."},{"key":"422441_CR17","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L., & Valiant, L.G. (1988). Computational limitations on learning from examples. Journal of the ACM, 35, 965\u2013984.","journal-title":"Journal of the ACM"},{"key":"422441_CR18","volume-title":"Principles of neurodynamics","author":"F. Rosenblatt","year":"1962","unstructured":"Rosenblatt, F. (1962). Principles of neurodynamics. New York: Spartan Books."},{"key":"422441_CR19","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5236.001.0001","volume-title":"Parallel distributed processing","author":"D.E. Rumelhart","year":"1986","unstructured":"Rumelhart, D.E., & McClelland, J.L. (1986). Parallel distributed processing. Cambridge, MA: MIT Press."},{"key":"422441_CR20","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G. (1984). A theory of the learnable. Communications of the ACM, 27, 1134\u20131142.","journal-title":"Communications of the ACM"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1022653511837.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1022653511837\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1022653511837.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T11:42:43Z","timestamp":1752147763000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1022653511837"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,3]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,3]]}},"alternative-id":["422441"],"URL":"https:\/\/doi.org\/10.1023\/a:1022653511837","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,3]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}