{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:03:29Z","timestamp":1775282609508,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"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":[[2003,6]]},"DOI":"10.1023\/a:1022949332276","type":"journal-article","created":{"date-parts":[[2003,4,7]],"date-time":"2003-04-07T18:16:51Z","timestamp":1049739411000},"page":"217-238","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":37,"title":["Boosting and Hard-Core Set Construction"],"prefix":"10.1007","volume":"51","author":[{"given":"Adam R.","family":"Klivans","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5120297_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai, L., Fortnow, L., Nisan, N., & Wigderson, A. (1993). BPP has subexponential time simulations unless exptime has publishable proofs. Computational Complexity, 3, 307\u2013318.","journal-title":"Computational Complexity"},{"key":"5120297_CR2","doi-asserted-by":"crossref","unstructured":"Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., & Rudich, S. (1994). Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In Proceedings of the Twenty-Sixth Annual Symposium on Theory of Computing (pp. 253\u2013262). ACM.","DOI":"10.1145\/195058.195147"},{"issue":"4","key":"5120297_CR3","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. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36:4, 929\u2013965.","journal-title":"Journal of the ACM"},{"key":"5120297_CR4","doi-asserted-by":"crossref","unstructured":"Boneh, D., & Lipton, R. (1993). Amplification of weak learning over the uniform distribution. In Proceedings of the Sixth Annual Workshop on Computational Learning Theory (pp. 347\u2013351). ACM.","DOI":"10.1145\/168304.168372"},{"key":"5120297_CR5","doi-asserted-by":"crossref","unstructured":"Bshouty, N., Jackson, J., & Tamon, C. (1999). More efficient PAC learning of DNF with membership queries under the uniform distribution. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory (pp. 286\u2013295).","DOI":"10.1145\/307400.307472"},{"key":"5120297_CR6","first-page":"479","volume":"8","author":"H. Drucker","year":"1996","unstructured":"Drucker, H., & Cortes, C. (1996). Boosting decision trees. In Advances in Neural Information Processing Systems 8 (pp. 479\u2013485).","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"6","key":"5120297_CR7","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1162\/neco.1994.6.6.1289","volume":"6","author":"H. Drucker","year":"1994","unstructured":"Drucker, H., Cortes, C., Jackel, L. D., Lecun, Y., & Vapnik, V. (1994). Boosting and other ensemble methods. Neural Computation, 6:6, 1289\u20131301.","journal-title":"Neural Computation"},{"issue":"4","key":"5120297_CR8","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1142\/S0218001493000352","volume":"7","author":"H. Drucker","year":"1993","unstructured":"Drucker, H., Schapire, R., & Simard, P. (1993a). Boosting performance in neural networks. International Journal of Pattern Recognition and Machine Intelligence, 7:4, 705\u2013719.","journal-title":"International Journal of Pattern Recognition and Machine Intelligence"},{"key":"5120297_CR9","first-page":"42","volume":"5","author":"H. Drucker","year":"1993","unstructured":"Drucker, H., Schapire, R., & Simard, P. (1993b). Improving performance in neural networks using a boosting algorithm. In Advances in Neural Information Processing Systems 5 (pp. 42\u201349).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"5120297_CR10","doi-asserted-by":"crossref","unstructured":"Freund, Y. (1990). Boosting a weak learning algorithm by majority. In Proceedings of the Third Annual Workshop on Computational Learning Theory (pp. 202\u2013216).","DOI":"10.1016\/B978-1-55860-146-8.50019-9"},{"key":"5120297_CR11","doi-asserted-by":"crossref","unstructured":"Freund, Y. (1992). An improved boosting algorithm and its implications on learning complexity. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory (pp. 391\u2013398).","DOI":"10.1145\/130385.130429"},{"issue":"2","key":"5120297_CR12","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1006\/inco.1995.1136","volume":"121","author":"Y. Freund","year":"1995","unstructured":"Freund, Y. (1995). Boosting a weak learning algorithm by majority. Information and Computation, 121:2, 256\u2013285.","journal-title":"Information and Computation"},{"issue":"1","key":"5120297_CR13","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1006\/jcss.1997.1504","volume":"55","author":"Y. Freund","year":"1997","unstructured":"Freund, Y., & Schapire, R. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55:1, 119\u2013139.","journal-title":"Journal of Computer and System Sciences"},{"key":"5120297_CR14","unstructured":"Goldreich, O., Nisan, N., & Wigderson, A. (1995). On Yao's xor-lemma. Electronic Colloquium on Computational Complexity, TR95-050."},{"key":"5120297_CR15","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R. (1995). Hard-core distributions for somewhat hard problems. In Proceedings of the Thirty-Sixth Annual Symposium on Foundations of Computer Science (pp. 538\u2013545). IEEE.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"5120297_CR16","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., & Widgerson, A. (1997). P = BPP unless E has subexponential circuits: Derandomizing the xor lemma. In Proceedings of the Twenty-Ninth Annual Symposium on Theory of Computing (pp. 220\u2013229).","DOI":"10.1145\/258533.258590"},{"key":"5120297_CR17","unstructured":"Jackson, J. (1995). The Harmonic sieve: A novel application of Fourier analysis to machine learning theory and practice. Ph.D. Thesis, Carnegie Mellon University."},{"key":"5120297_CR18","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"J. Jackson","year":"1997","unstructured":"Jackson, J. (1997). An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55, 414\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"5120297_CR19","unstructured":"Jackson, J. (2002). Personal communication."},{"key":"5120297_CR20","first-page":"654","volume":"8","author":"J. Jackson","year":"1996","unstructured":"Jackson, J., & Craven, M. (1996). Learning sparse perceptrons. In Advances in Neural Information Processing Systems 8 (pp. 654\u2013660).","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"1","key":"5120297_CR21","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., & Valiant, L. (1994). Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM, 41:1, 67\u201395.","journal-title":"Journal of the ACM"},{"key":"5120297_CR22","doi-asserted-by":"crossref","unstructured":"Klivans, A., & Servedio, R. (2001). Learning DNF in time \n$$2^{\\tilde O(n^{{1 \\mathord{\\left\/ {\\vphantom {1 3}} \\right. \\kern-\\nulldelimiterspace} 3}} )} $$\n. In Proceedings of the Twenty-Sixth Annual Symposium on Theory of Computing (pp. 258\u2013265).","DOI":"10.1145\/380752.380809"},{"issue":"1","key":"5120297_CR23","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"Levin, L. (1986). Average case complete problems. SIAM Journal on Computing, 15:1, 285\u2013286.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"5120297_CR24","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1145\/321879.321882","volume":"22","author":"D. Muller","year":"1975","unstructured":"Muller, D., & Preparata, F. (1975). Bounds to complexities of networks for sorting and for switching. Journal of the ACM, 22:2, 195\u2013201.","journal-title":"Journal of the ACM"},{"key":"5120297_CR25","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., & Wigderson, A. (1994). Hardness versus randomness. Journal of Computer and System Sciences, 49, 149\u2013167.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"5120297_CR26","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1023\/A:1022648800760","volume":"5","author":"R. Schapire","year":"1990","unstructured":"Schapire, R. (1990). The strength of weak learnability. Machine Learning, 5:2, 197\u2013227.","journal-title":"Machine Learning"},{"key":"5120297_CR27","doi-asserted-by":"crossref","unstructured":"Schapire, R., & Singer,Y. (1998). Improved boosting algorithms using confidence-rated predictions. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory (pp. 80\u201391).","DOI":"10.1145\/279943.279960"},{"key":"5120297_CR28","doi-asserted-by":"crossref","unstructured":"Servedio, R. (2001). Smooth boosting and learning with malicious noise. In Proceedings of the Fourteenth Annual Conference on Computational Learning Theory (pp. 473\u2013489).","DOI":"10.1007\/3-540-44581-1_31"},{"key":"5120297_CR29","doi-asserted-by":"crossref","unstructured":"Shaltiel, R. (2001). Towards proving strong direct product theorems. In Proceedings of the Sixteenth Conference on Computational Complexity (pp. 107\u2013117).","DOI":"10.1109\/CCC.2001.933878"},{"issue":"2","key":"5120297_CR30","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., & Vadhan, S. (2001). Pseudorandom generators without the xor lemma. Journal of Computer and System Sciences, 62:2, 236\u2013266.","journal-title":"Journal of Computer and System Sciences"},{"issue":"11","key":"5120297_CR31","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"Valiant, L. (1984). A theory of the learnable. Communications of the ACM, 27:11, 1134\u20131142.","journal-title":"Communications of the ACM"},{"key":"5120297_CR32","unstructured":"Wigderson, A. (1999). Personal communication."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1022949332276.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1022949332276\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1022949332276.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T11:43:48Z","timestamp":1752147828000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1022949332276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,6]]}},"alternative-id":["5120297"],"URL":"https:\/\/doi.org\/10.1023\/a:1022949332276","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,6]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}