{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:35:24Z","timestamp":1725471324743},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540352945"},{"type":"electronic","value":"9783540352969"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11776420_26","type":"book-chapter","created":{"date-parts":[[2006,9,28]],"date-time":"2006-09-28T10:49:15Z","timestamp":1159440555000},"page":"335-349","source":"Crossref","is-referenced-by-count":6,"title":["Improved Lower Bounds for Learning Intersections of Halfspaces"],"prefix":"10.1007","author":[{"given":"Adam R.","family":"Klivans","sequence":"first","affiliation":[]},{"given":"Alexander A.","family":"Sherstov","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A., Pitassi, T.: Learnability and automatizability. In: Proceedings of the 45th Annual Symposium on Foundations of Computer Science (FOCS) (2004)","DOI":"10.1109\/FOCS.2004.36"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1145\/103418.103461","volume-title":"STOC 1991: Proceedings of the twenty-third annual ACM symposium on Theory of computing","author":"J. Aspnes","year":"1991","unstructured":"Aspnes, J., Beigel, R., Furst, M., Rudich, S.: The expressive power of voting polynomials. In: STOC 1991: Proceedings of the twenty-third annual ACM symposium on Theory of computing, pp. 402\u2013409. ACM Press, New York (1991)"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/103418.103426","volume-title":"STOC 1991: Proceedings of the twenty-third annual ACM symposium on Theory of computing","author":"R. Beigel","year":"1991","unstructured":"Beigel, R., Reingold, N., Spielman, D.: PP is closed under intersection. In: STOC 1991: Proceedings of the twenty-third annual ACM symposium on Theory of computing, pp. 1\u20139. ACM Press, New York (1991)"},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1145\/195058.195147","volume-title":"STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing","author":"A. Blum","year":"1994","unstructured":"Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., Rudich, S.: Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In: STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 253\u2013262. ACM Press, New York (1994)"},{"issue":"4","key":"26_CR5","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A. Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM\u00a050(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"issue":"2","key":"26_CR6","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1137\/0403015","volume":"3","author":"J. Bruck","year":"1990","unstructured":"Bruck, J.: Harmonic analysis of polynomial threshold functions. SIAM J. Discrete Math.\u00a03(2), 168\u2013177 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"26_CR7","unstructured":"Jackson, J.C.: The harmonic sieve: A novel application of Fourier analysis to machine learning theory and practice. PhD thesis, Carnegie Mellon University (1995)"},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1145\/167088.167200","volume-title":"STOC 1993: Proceedings of the twenty-fifth annual ACM symposium on theory of computing","author":"M. Kearns","year":"1993","unstructured":"Kearns, M.: Efficient noise-tolerant learning from statistical queries. In: STOC 1993: Proceedings of the twenty-fifth annual ACM symposium on theory of computing, pp. 392\u2013401. ACM Press, New York (1993)"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Klivans, A., O\u2019Donnell, R., Servedio, R.: Learning intersections and thresholds of halfspaces. In: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, pp. 177\u2013186 (2002)","DOI":"10.1109\/SFCS.2002.1181894"},{"key":"26_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-540-27819-1_24","volume-title":"Learning Theory","author":"A.R. Klivans","year":"2004","unstructured":"Klivans, A.R., Servedio, R.A.: Learning intersections of halfspaces with a margin. In: Shawe-Taylor, J., Singer, Y. (eds.) COLT 2004. LNCS, vol.\u00a03120, pp. 348\u2013362. Springer, Heidelberg (2004)"},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1145\/195058.195103","volume-title":"STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing","author":"M. Krause","year":"1994","unstructured":"Krause, M., Pudl\u00e1k, P.: On the computational power of depth 2 circuits with threshold and modulo gates. In: STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 48\u201357. ACM Press, New York (1994)"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1145\/103418.103466","volume-title":"STOC 1991: Proceedings of the twenty-third annual ACM symposium on Theory of computing","author":"E. Kushilevitz","year":"1991","unstructured":"Kushilevitz, E., Mansour, Y.: Learning decision trees using the fourier spectrum. In: STOC 1991: Proceedings of the twenty-third annual ACM symposium on Theory of computing, pp. 455\u2013464. ACM Press, New York (1991)"},{"issue":"1\/2","key":"26_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/PL00013834","volume":"22","author":"S. Kwek","year":"1998","unstructured":"Kwek, S., Pitt, L.: PAC learning intersections of halfspaces with membership queries. Algorithmica\u00a022(1\/2), 53\u201375 (1998)","journal-title":"Algorithmica"},{"key":"26_CR14","volume-title":"Perceptrons: expanded edition","author":"M.L. Minsky","year":"1988","unstructured":"Minsky, M.L., Papert, S.A.: Perceptrons: expanded edition. MIT Press, Cambridge (1988)"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1145\/780542.780592","volume-title":"STOC 2003: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing","author":"R. O\u2019Donnell","year":"2003","unstructured":"O\u2019Donnell, R., Servedio, R.A.: New degree bounds for polynomial threshold functions. In: STOC 2003: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 325\u2013334. ACM Press, New York (2003)"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Saks, M.E.: Slicing the hypercube. Surveys in combinatorics, 211\u2013255 (1993)","DOI":"10.1017\/CBO9780511662089.009"},{"issue":"11","key":"26_CR17","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM\u00a027(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"key":"26_CR18","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"}],"container-title":["Lecture Notes in Computer Science","Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11776420_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:06:54Z","timestamp":1605625614000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11776420_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540352945","9783540352969"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11776420_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}