{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T19:44:46Z","timestamp":1760384686965,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667483"},{"type":"electronic","value":"9783540467694"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46769-6_17","type":"book-chapter","created":{"date-parts":[[2007,2,28]],"date-time":"2007-02-28T12:42:39Z","timestamp":1172666559000},"page":"206-218","source":"Crossref","is-referenced-by-count":6,"title":["PAC Learning with Nasty Noise"],"prefix":"10.1007","author":[{"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[]},{"given":"Nadav","family":"Eiron","sequence":"additional","affiliation":[]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,5,19]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"J. A. Aslam and S. E. Decatur, \u201cGeneral Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Boosting\u201d, FOCS93, pp. 282\u2013291, 1993.","DOI":"10.1109\/SFCS.1993.366859"},{"key":"17_CR2","first-page":"343","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin and P. Laird, \u201cLearning from Noisy Examples\u201d, Machine Learning, Vol. 2, pp. 343\u2013370, 1988.","journal-title":"Machine Learning"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"S. Ben-David, N. H. Bshouty and E. Kushilevitz, \u201cA Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes\u201d, STOC97, pp. 324\u2013333, 1997.","DOI":"10.1145\/258533.258614"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(98)00000-6","volume":"86","author":"S. Ben-David","year":"1998","unstructured":"S. Ben-David and A. Litman, \u201cCombinatorial Variability of Vapnik-Chervonenkis Classes with Applications to Sample Compression Schemes\u201d, Discrete Applied Math 86, pp. 3\u201325, 1998.","journal-title":"Discrete Applied Math"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chalasani, S. A. Goldman, and D. K. Slonim, \u201cLearning with Unreliable Boundary Queries\u201d, COLT95, pp. 98\u2013107, 1995.","DOI":"10.1145\/225298.225310"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"A. Blum, M. Furst, J. Jackson, M. J. Kearns, Y. Mansour, and S. Rudich, \u201cWeakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis\u201d, STOC94, 1994.","DOI":"10.1145\/195058.195147"},{"issue":"4","key":"17_CR7","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler and M. K. Warmuth, \u201cLearnability and the Vapnik-Chervonenkis dimension\u201d, J. of the ACM, 36(4), pp. 929\u2013965, 1989.","journal-title":"J. of the ACM"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, \u201cA New Composition Theorem for Learning Algorithms\u201d, STOC98, pp. 583\u2013589, 1998.","DOI":"10.1145\/276698.276873"},{"key":"17_CR9","unstructured":"N. H. Bshouty, N. Eiron and E. Kushilevitz, \u201cPAC Learning with Nasty Noise\u201d, Technical Report CS0693, Department of Computer Science, The Technion \u2014 Israel Institute of Technology."},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, S. A. Goldman, H. D. Mathias, S. Suri, and H. Tamaki, \u201cNoise-Tolerant Distribution-Free Learning of General Geometric Concepts\u201d, STOC96, pp. 151\u2013160, 1996.","DOI":"10.1145\/237814.237854"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"N. Cesa-Bianchi, E. Dichterman, P. Fischer, and H. U. Simon, \u201cNoise-Tolerant Learning near the Information-Theoretic bound\u201d, STOC96, pp. 141\u2013150, 1996.","DOI":"10.1145\/237814.237849"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"N. Cesa-Bianchi, P. Fischer, E. Shamir and H. U. Simon, \u201cRandomized hypotheses and Minimum Disagreement hypotheses for Learning with Noise\u201d, proceedings of EuroCOLT 97, pp. 119\u2013133, 1997.","DOI":"10.1007\/3-540-62685-9_11"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"S. E. Decatur, \u201cLearning in Hybrid Noise Environments Using Statistical Queries\u201d, in Learning from Data: Artificial Intelligence and Statistics V, D. Fisher and H. J. Lenz, (Eds.), 1996.","DOI":"10.1007\/978-1-4612-2404-4_25"},{"key":"17_CR14","unstructured":"S. E. Decatur, \u201cPAC Learning with Constant-Partition Classification Noise and Applications to Decision Tree Induction\u201d, Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics, pp. 147\u2013156, 1997."},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"S. E. Decatur and R. Gennaro, \u201cOn Learning from Noisy and Incomplete Examples\u201d, COLT95, pp. 353\u2013360, 1995.","DOI":"10.1145\/225298.225341"},{"issue":"301","key":"17_CR16","doi-asserted-by":"publisher","first-page":"13","DOI":"10.2307\/2282952","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"W. Hoeffding, \u201cProbability Inequalities for Sums of Bounded Random Variables\u201d, J. of the American Statistical Association, 58(301), pp. 13\u201330, 1963.","journal-title":"J. of the American Statistical Association"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"M. Kearns, \u201cEfficient Noise-Tolerant Learning from Statistical Queries\u201d, Proc. 25th ACM Symposium on the Theory of Computing, pp. 392\u2013401, 1993.","DOI":"10.1145\/167088.167200"},{"key":"17_CR18","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1137\/0222052","volume":"22","author":"M. J. Kearns","year":"1993","unstructured":"M. J. Kearns and M. Li, \u201cLearning in the Presence of Malicious Errors\u201d, SIAM J. on Computing, 22:807\u2013837, 1993.","journal-title":"SIAM J. on Computing"},{"issue":"2","key":"17_CR19","first-page":"115","volume":"17","author":"M. J. Kearns","year":"1994","unstructured":"M. J. Kearns, R. E. Schapire, and L. M. Sellie, \u201cToward Efficient Agnostic Learning\u201d, Machine Learning, vol. 17(2), pp. 115\u2013142, 1994.","journal-title":"Machine Learning"},{"key":"17_CR20","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"N. Sauer, \u201cOn the Density of Families of sets\u201d, Journal of Combinatorial Theory, 13:145\u2013147, 1972.","journal-title":"Journal of Combinatorial Theory"},{"key":"17_CR21","unstructured":"R. E. Schapire, \u201cThe Design and Analysis of Efficient Learning Algorithms\u201d, MIT Press, 1991."},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1214\/aop\/1176988847","volume":"22","author":"M. Talagrand","year":"1994","unstructured":"M. Talagrand, \u201cSharper Bounds for Gaussian and Empirical Processes\u201d, Annals of Probability, 22:28\u201376, 1994.","journal-title":"Annals of Probability"},{"issue":"11","key":"17_CR23","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant, \u201cA Theory of the Learnable\u201d, Comm. ACM, 27(11):1134\u20131142, 1984.","journal-title":"Comm. ACM"},{"key":"17_CR24","unstructured":"L. G. Valiant, \u201cLearning Disjunctions of Conjunctions\u201d, IJCAI85, pp. 560\u2013566, 1985."},{"issue":"2","key":"17_CR25","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"V. N. Vapnik and A. Y. Chervonenkis, \u201cOn the Uniform Convergence of Relative Frequencies of Events to Their Probabilities\u201d, Theory Probab. Appl. 16, no. 2 pp. 264\u2013280, 1971.","journal-title":"Theory Probab. Appl."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46769-6_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T09:39:57Z","timestamp":1736847597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46769-6_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667483","9783540467694"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-46769-6_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}