{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:43:39Z","timestamp":1725565419642},"publisher-location":"Berlin, Heidelberg","reference-count":33,"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_16","type":"book-chapter","created":{"date-parts":[[2010,9,14]],"date-time":"2010-09-14T06:05:39Z","timestamp":1284444339000},"page":"224-238","source":"Crossref","is-referenced-by-count":6,"title":["Toward Attribute Efficient Learning of Decision Lists and Parities"],"prefix":"10.1007","author":[{"given":"Adam R.","family":"Klivans","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning. Machine Learning\u00a02, 319\u2013342 (1988)","journal-title":"Machine Learning"},{"key":"16_CR2","first-page":"1224","volume":"13","author":"J. Barzdin","year":"1972","unstructured":"Barzdin, J., Freivald, R.: On the prediction of general recursive functions. Soviet Mathematics Doklady\u00a013, 1224\u20131228 (1972)","journal-title":"Soviet Mathematics Doklady"},{"key":"16_CR3","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"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Blum, A.: Learning boolean functions in an infinite attribute space. In: Proceedings of the Twenty-Second Annual Symposium on Theory of Computing, pp. 64\u201372 (1990)","DOI":"10.1145\/100216.100224"},{"key":"16_CR5","unstructured":"Blum, A.: On-line algorithms in machine learning (1996), available at http:\/\/www.cs.cmu.edu\/~avrim\/Papers\/pubs.html"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1007335615132","volume":"26","author":"A. Blum","year":"1997","unstructured":"Blum, A.: Empirical support for winnow and weighted-majority algorithms: results on a calendar scheduling domain. Machine Learning\u00a026, 5\u201323 (1997)","journal-title":"Machine Learning"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1006\/jcss.1995.1004","volume":"50","author":"A. Blum","year":"1995","unstructured":"Blum, A., Hellerstein, L., Littlestone, N.: Learning in the presence of finitely or infinitely many irrelevant attributes. Journal of Computer and System Sciences\u00a050, 32\u201340 (1995)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1-2","key":"16_CR8","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0004-3702(97)00063-5","volume":"97","author":"A. Blum","year":"1997","unstructured":"Blum, A., Langley, P.: Selection of relevant features and examples in machine learning. Artificial Intelligence\u00a097(1-2), 245\u2013271 (1997)","journal-title":"Artificial Intelligence"},{"key":"16_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":"16_CR10","doi-asserted-by":"crossref","unstructured":"Dhagat, A., Hellerstein, L.: Pac learning with irrelevant attributes. In: Proceedings of the Thirty-Fifth Annual Symposium on Foundations of Computer Science, pp. 64\u201374 (1994)","DOI":"10.1109\/SFCS.1994.365704"},{"issue":"3","key":"16_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0890-5401(89)90001-1","volume":"82","author":"A. Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D.: Learning decision trees from random examples. Information and Computation\u00a082(3), 231\u2013246 (1989)","journal-title":"Information and Computation"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1023\/A:1007545901558","volume":"34","author":"A.R. Golding","year":"1999","unstructured":"Golding, A.R., Roth, D.: A winnow-based approach to spelling correction. Machine Learning\u00a034, 107\u2013130 (1999)","journal-title":"Machine Learning"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"M. Goldmann","year":"1992","unstructured":"Goldmann, M., Hastad, J., Razborov, A.: Majority gates vs. general weighted threshold gates. Computational Complexity\u00a02, 277\u2013300 (1992)","journal-title":"Computational Complexity"},{"key":"16_CR14","unstructured":"Haussler, D.: Space efficient learning algorithms. Technical Report UCSC-CRL- 88-2, University of California at Santa Cruz (1988)"},{"issue":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/0221019","volume":"21","author":"D. Helmbold","year":"1992","unstructured":"Helmbold, D., Sloan, R., Warmuth, M.: Learning integer lattices. SIAM Journal on Computing\u00a021(2), 240\u2013266 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"1-2","key":"16_CR16","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0004-3702(97)00039-8","volume":"97","author":"J. Kivinen","year":"1997","unstructured":"Kivinen, J., Warmuth, M., Auer, P.: The perceptron algorithm vs. winnow: linear vs. logarithmic mistake bounds when few input variables are relevant. Artificial Intelligence\u00a097(1-2), 325\u2013343 (1997)","journal-title":"Artificial Intelligence"},{"key":"16_CR17","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 (2002)","DOI":"10.1109\/SFCS.2002.1181894"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Klivans, A., Servedio, R.: Learning dnf in time 2\u00f5(n1\/3). In: Proceedings of the Thirty-Third Annual Symposium on Theory of Computing, pp. 258\u2013265 (2001)","DOI":"10.1145\/380752.380809"},{"issue":"4","key":"16_CR19","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/s000370050015","volume":"7","author":"M. Krause","year":"1998","unstructured":"Krause, M., Pudlak, P.: Computing boolean functions by polynomials and threshold circuits. Computational Complexity\u00a07(4), 346\u2013370 (1998)","journal-title":"Computational Complexity"},{"key":"16_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1007\/3-540-45841-7_30","volume-title":"STACS 2002","author":"M. Krause","year":"2002","unstructured":"Krause, M.: On the computational power of boolean decision lists. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, p. 372. Springer, Heidelberg (2002)"},{"key":"16_CR21","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"Littlestone, N.: Learning quickly when irrelevant attributes abound: a new linearthreshold algorithm. Machine Learning\u00a02, 285\u2013318 (1988)","journal-title":"Machine Learning"},{"key":"16_CR22","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/B978-0-08-094829-4.50022-2","volume-title":"Proceedings of the Second Annual Workshop on Computational Learning Theory","author":"Nick Littlestone","year":"1989","unstructured":"Littlestone, N.: From online to batch learning. In: Proceedings of the Second Annual Workshop on Computational Learning Theory, pp. 269\u2013284 (1989)"},{"key":"16_CR23","unstructured":"Littlestone, N.: Mistake bounds and logarithmic linear-threshold learning algorithms. PhD thesis, University of California at Santa Cruz (1989)"},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0004-3702(82)90040-6","volume":"18","author":"T. Mitchell","year":"1982","unstructured":"Mitchell, T.: Generalization as search. Artificial Intelligence\u00a018, 203\u2013226 (1982)","journal-title":"Artificial Intelligence"},{"issue":"2","key":"16_CR25","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1109\/TEC.1961.5219204","volume":"EC10","author":"J. Myhill","year":"1961","unstructured":"Myhill, J., Kautz, W.: On the size of weights required for linear-input switching functions. IRE Trans. on Electronic Computers\u00a0EC10(2), 288\u2013290 (1961)","journal-title":"IRE Trans. on Electronic Computers"},{"key":"16_CR26","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1162\/153244303765208395","volume":"3","author":"Z. Nevo","year":"2002","unstructured":"Nevo, Z., El-Yaniv, R.: On online learning of decision lists. Journal of Machine Learning Research\u00a03, 271\u2013301 (2002)","journal-title":"Journal of Machine Learning Research"},{"key":"16_CR27","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 (2003)","DOI":"10.1145\/780542.780592"},{"issue":"3","key":"16_CR28","first-page":"229","volume":"2","author":"R. Rivest","year":"1987","unstructured":"Rivest, R.: Learning decision lists. Machine Learning\u00a02(3), 229\u2013246 (1987)","journal-title":"Machine Learning"},{"issue":"1","key":"16_CR29","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1006\/jcss.1999.1666","volume":"60","author":"R. Servedio","year":"2000","unstructured":"Servedio, R.: Computational sample complexity and attribute-efficient learning. Journal of Computer and System Sciences\u00a060(1), 161\u2013178 (2000)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"16_CR30","doi-asserted-by":"publisher","first-page":"1358","DOI":"10.1137\/S0097539798340928","volume":"31","author":"R. Servedio","year":"2002","unstructured":"Servedio, R.: Perceptron, Winnow and PAC learning. SIAM Journal on Computing\u00a031(5), 1358\u20131369 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR31","unstructured":"Spielman, D.: Personal communication (2003)"},{"key":"16_CR32","first-page":"171","volume-title":"Lecture Notes in Computer Science","author":"Ryuhei Uehara","year":"1997","unstructured":"Uehara, R., Tsuchida, K., Wegener, I.: Optimal attribute-efficient learning of disjunction, parity, and threshold functions. In: Proceedings of the Third European Conference on Computational Learning Theory, pp. 171\u2013184 (1997)"},{"issue":"2","key":"16_CR33","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1023\/A:1007678005361","volume":"37","author":"L. Valiant","year":"1999","unstructured":"Valiant, L.: Projection learning. Machine Learning\u00a037(2), 115\u2013130 (1999)","journal-title":"Machine Learning"}],"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_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:22:57Z","timestamp":1605759777000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27819-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540222828","9783540278191"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27819-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}