{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T17:55:52Z","timestamp":1773510952441,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642029264","type":"print"},{"value":"9783642029271","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_51","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T04:37:10Z","timestamp":1246682230000},"page":"609-621","source":"Crossref","is-referenced-by-count":9,"title":["Learning Halfspaces with Malicious Noise"],"prefix":"10.1007","author":[{"given":"Adam R.","family":"Klivans","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip M.","family":"Long","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"51_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pp. 724\u2013733 (1993)","DOI":"10.1109\/SFCS.1993.366815"},{"issue":"1\/2","key":"51_CR2","first-page":"35","volume":"22","author":"A. Blum","year":"1997","unstructured":"Blum, A., Frieze, A., Kannan, R., Vempala, S.: A polynomial time algorithm for learning noisy linear threshold functions. Algorithmica\u00a022(1\/2), 35\u201352 (1997)","journal-title":"Algorithmica"},{"issue":"4","key":"51_CR3","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. Journal of the ACM\u00a036(4), 929\u2013965 (1989)","journal-title":"Journal of the ACM"},{"key":"51_CR4","doi-asserted-by":"crossref","unstructured":"Bshouty, N.H., Li, Y., Long, P.M.: Using the doubling dimension to analyze the generalization of learning algorithms. J. Comp. Sys. Sci. (to appear, 2009)","DOI":"10.1016\/j.jcss.2009.01.003"},{"issue":"2","key":"51_CR5","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2003.07.013","volume":"68","author":"J. Dunagan","year":"2004","unstructured":"Dunagan, J., Vempala, S.: Optimal outlier removal in high-dimensional spaces. J. Computer & System Sciences\u00a068(2), 335\u2013373 (2004)","journal-title":"J. Computer & System Sciences"},{"key":"51_CR6","doi-asserted-by":"crossref","unstructured":"Feldman, V., Gopalan, P., Khot, S., Ponnuswami, A.: New results for learning noisy parities and halfspaces. In: Proc. FOCS, pp. 563\u2013576 (2006)","DOI":"10.1109\/FOCS.2006.51"},{"issue":"3","key":"51_CR7","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1023\/A:1007662407062","volume":"37","author":"Y. Freund","year":"1999","unstructured":"Freund, Y., Schapire, R.E.: Large margin classification using the perceptron algorithm. Machine Learning\u00a037(3), 277\u2013296 (1999)","journal-title":"Machine Learning"},{"key":"51_CR8","first-page":"101","volume":"4","author":"D. Gavinsky","year":"2003","unstructured":"Gavinsky, D.: Optimally-smooth adaptive boosting and application to agnostic learning. Journal of Machine Learning Research\u00a04, 101\u2013117 (2003)","journal-title":"Journal of Machine Learning Research"},{"key":"51_CR9","first-page":"543","volume-title":"Proc. FOCS","author":"V. Guruswami","year":"2006","unstructured":"Guruswami, V., Raghavendra, P.: Hardness of learning halfspaces with noise. In: Proc. FOCS, pp. 543\u2013552. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"51_CR10","unstructured":"Jolliffe, I.T.: Principal Component Analysis. Springer Series in Statistics (2002)"},{"issue":"6","key":"51_CR11","doi-asserted-by":"publisher","first-page":"1777","DOI":"10.1137\/060649057","volume":"37","author":"A. Kalai","year":"2008","unstructured":"Kalai, A., Klivans, A., Mansour, Y., Servedio, R.: Agnostically learning halfspaces. SIAM Journal on Computing\u00a037(6), 1777\u20131805 (2008)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"51_CR12","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1137\/0222052","volume":"22","author":"M. Kearns","year":"1993","unstructured":"Kearns, M., Li, M.: Learning in the presence of malicious errors. SIAM Journal on Computing\u00a022(4), 807\u2013837 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"2\/3","key":"51_CR13","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1023\/A:1022615600103","volume":"17","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Schapire, R., Sellie, L.: Toward Efficient Agnostic Learning. Machine Learning\u00a017(2\/3), 115\u2013141 (1994)","journal-title":"Machine Learning"},{"key":"51_CR14","doi-asserted-by":"crossref","unstructured":"Klivans, A., Long, P., Servedio, R.: Learning Halfspaces with Malicious Noise (2009), http:\/\/www.cs.columbia.edu\/~rocco\/papers\/icalp09malicious.html","DOI":"10.1007\/978-3-642-02927-1_51"},{"key":"51_CR15","doi-asserted-by":"crossref","unstructured":"Klivans, A., Sherstov, A.: Cryptographic hardness for learning intersections of halfspaces. In: Proc. FOCS, pp. 553\u2013562 (2006)","DOI":"10.1109\/FOCS.2006.24"},{"key":"51_CR16","first-page":"285","volume":"2","author":"N. Littlestone","year":"1987","unstructured":"Littlestone, N.: Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm. Machine Learning\u00a02, 285\u2013318 (1987)","journal-title":"Machine Learning"},{"key":"51_CR17","doi-asserted-by":"crossref","unstructured":"Littlestone, N.: Redundant noisy attributes, attribute errors, and linear-threshold learning using Winnow. In: Proc. COLT, pp. 147\u2013156 (1991)","DOI":"10.1016\/B978-1-55860-213-7.50017-1"},{"key":"51_CR18","first-page":"381","volume-title":"Computational Learning Theory and Natural Learning Systems. Constraints and Prospects","author":"W. Maass","year":"1994","unstructured":"Maass, W., Turan, G.: How fast can a threshold gate learn? In: Computational Learning Theory and Natural Learning Systems. Constraints and Prospects, vol.\u00a0I, pp. 381\u2013414. MIT Press, Cambridge (1994)"},{"issue":"4","key":"51_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0020-0190(98)00165-3","volume":"68","author":"Y. Mansour","year":"1998","unstructured":"Mansour, Y., Parnas, M.: Learning conjunctions with noise under product distributions. Information Processing Letters\u00a068(4), 189\u2013196 (1998)","journal-title":"Information Processing Letters"},{"key":"51_CR20","unstructured":"Novikoff, A.: On convergence proofs on perceptrons. In: Proceedings of the Symposium on Mathematical Theory of Automata, vol.\u00a0XII, pp. 615\u2013622 (1962)"},{"key":"51_CR21","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1037\/h0042519","volume":"65","author":"F. Rosenblatt","year":"1958","unstructured":"Rosenblatt, F.: The Perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review\u00a065, 386\u2013407 (1958)","journal-title":"Psychological Review"},{"key":"51_CR22","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1023\/A:1007614523901","volume":"37","author":"R. Schapire","year":"1999","unstructured":"Schapire, R., Singer, Y.: Improved boosting algorithms using confidence-rated predictions. Machine Learning\u00a037, 297\u2013336 (1999)","journal-title":"Machine Learning"},{"key":"51_CR23","unstructured":"Servedio, R.: PAC analogues of Perceptron and Winnow via boosting the margin. In: Proc. COLT, pp. 148\u2013157 (2000)"},{"key":"51_CR24","unstructured":"Servedio, R.: Efficient Algorithms in Computational Learning Theory. PhD thesis, Harvard University (2001)"},{"key":"51_CR25","first-page":"633","volume":"4","author":"R. Servedio","year":"2003","unstructured":"Servedio, R.: Smooth boosting and learning with malicious noise. Journal of Machine Learning Research\u00a04, 633\u2013648 (2003)","journal-title":"Journal of Machine Learning Research"},{"key":"51_CR26","volume-title":"An introduction to support vector machines","author":"J. Shawe-Taylor","year":"2000","unstructured":"Shawe-Taylor, J., Cristianini, N.: An introduction to support vector machines. Cambridge University Press, Cambridge (2000)"},{"key":"51_CR27","unstructured":"Valiant, L.: Learning disjunctions of conjunctions. In: Proceedings of the Ninth International Joint Conference on Artificial Intelligence, pp. 560\u2013566 (1985)"},{"key":"51_CR28","unstructured":"Xu, H., Caramanis, C., Mannor, S.: Principal component analysis with contaminated data: The high dimensional case. In: JMLR (to appear, 2009)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T02:54:10Z","timestamp":1558407250000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}