{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T05:33:05Z","timestamp":1740547985507,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540222828"},{"type":"electronic","value":"9783540278191"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27819-1_24","type":"book-chapter","created":{"date-parts":[[2010,9,14]],"date-time":"2010-09-14T06:05:39Z","timestamp":1284444339000},"page":"348-362","source":"Crossref","is-referenced-by-count":9,"title":["Learning Intersections of Halfspaces with a Margin"],"prefix":"10.1007","author":[{"given":"Adam R.","family":"Klivans","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"24_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D. Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Journal of Computer and System Sciences\u00a066(4), 671\u2013687 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0166-218X(94)00008-2","volume":"61","author":"M. Anthony","year":"1995","unstructured":"Anthony, M.: Classification by polynomial surfaces. Discrete Applied Mathematics\u00a061, 91\u2013103 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Arriaga, R., Vempala, S.: An algorithmic theory of learning: Robust concepts and random projection. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 616\u2013623 (1999)","DOI":"10.1109\/SFFCS.1999.814637"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1162\/neco.1990.2.4.510","volume":"2","author":"E. Baum","year":"1991","unstructured":"Baum, E.: A polynomial time algorithm that learns two hidden unit nets. Neural Computation\u00a02, 510\u2013522 (1991)","journal-title":"Neural Computation"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/BF01263420","volume":"4","author":"R. Beigel","year":"1994","unstructured":"Beigel, R.: When do extra majority gates help? polylog(n) majority gates are equivalent to one. Computational Complexity\u00a04, 314\u2013324 (1994)","journal-title":"Computational Complexity"},{"issue":"2","key":"24_CR6","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jcss.1995.1017","volume":"50","author":"R. Beigel","year":"1995","unstructured":"Beigel, R., Reingold, N., Spielman, D.: PP is closed under intersection. Journal of Computer and System Sciences\u00a050(2), 191\u2013202 (1995)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"24_CR7","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1006\/jcss.1997.1475","volume":"54","author":"A. Blum","year":"1997","unstructured":"Blum, A., Kannan, R.: Learning an intersection of a constant number of halfspaces under a uniform distribution. Journal of Computer and System Sciences\u00a054(2), 371\u2013380 (1997)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"24_CR8","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":"24_CR9","volume-title":"Introduction to Approximation Theory","author":"E. Cheney","year":"1966","unstructured":"Cheney, E.: Introduction to Approximation Theory. McGraw-Hill, New York (1966)"},{"key":"24_CR10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801389","volume-title":"An introduction to Support Vector Machines (and other kernel-based learning methods)","author":"N. Cristianini","year":"2000","unstructured":"Cristianini, N., Shawe-Taylor, J.: An introduction to Support Vector Machines (and other kernel-based learning methods). Cambridge University Press, Cambridge (2000)"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Freund, Y., Schapire, R.: Large margin classification using the Perceptron algorithm. In: Proceedings of the Eleventh Annual Conference on Computational Learning Theory, pp. 209\u2013217 (1998)","DOI":"10.1145\/279943.279985"},{"key":"24_CR12","volume-title":"Learning Kernel Classifiers","author":"R. Herbrich","year":"2002","unstructured":"Herbrich, R.: Learning Kernel Classifiers. MIT Press, Cambridge (2002)"},{"key":"24_CR13","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W. Johnson","year":"1984","unstructured":"Johnson, W., Lindenstrauss, J.: Extensions of Lipshitz mapping into Hilbert space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"key":"24_CR14","volume-title":"Advances in Neural Information Processing Systems 14","author":"R. Khardon","year":"2002","unstructured":"Khardon, R., Roth, D., Servedio, R.: Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms. In: Dietterich, T.G., Becker, S., Ghahramani, Z. (eds.) Advances in Neural Information Processing Systems 14, MIT Press, Cambridge (2002)"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Klivans, A., O\u2019Donnell, R., Servedio, R.: Learning intersections and thresholds of halfspaces. In: Proceedings of the Forty-Third Annual Symposium on Foundations of Computer Science, pp. 177\u2013186 (2002)","DOI":"10.1109\/SFCS.2002.1181894"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"Klivans and R. Servedio. Learning DNF in time 2\u00d5 (n1\/3). In Proceedings of the Thirty-Third Annual Symposium on Theory of Computing, pages 258\u2013265, 2001.","DOI":"10.1145\/380752.380809"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1307\/mmj\/1028999029","volume":"11","author":"D.J. Newman","year":"1964","unstructured":"Newman, D.J.: Rational approximation to |x|. Michigan Mathematical Journal\u00a011, 11\u201314 (1964)","journal-title":"Michigan Mathematical Journal"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Servedio, R.: Extremal properties of polynomial threshold functions. In: Proceedings of the Eighteenth Annual Conference on Computational Complexity, pp. 3\u201312 (2003)","DOI":"10.1109\/CCC.2003.1214406"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Servedio, R.: New degree bounds for polynomial threshold functions. In: Proceedings of the 35th ACM Symposium on Theory of Computing, pp. 325\u2013334 (2003)","DOI":"10.1145\/780542.780592"},{"key":"24_CR20","doi-asserted-by":"crossref","unstructured":"Saks, M.: Slicing the hypercub. London Mathematical Society Lecture Note Series, vol.\u00a0187, pp. 211\u2013257 (1993)","DOI":"10.1017\/CBO9780511662089.009"},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Vempala, S.: A random sampling based algorithm for learning the intersection of halfspaces. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pp. 508\u2013513 (1997)","DOI":"10.1109\/SFCS.1997.646139"},{"key":"24_CR22","unstructured":"Vempala, S.: Personal communication (2004)"}],"container-title":["Lecture Notes in Computer Science","Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27819-1_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T19:56:38Z","timestamp":1740513398000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27819-1_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540222828","9783540278191"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27819-1_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}