{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,17]],"date-time":"2022-05-17T20:48:03Z","timestamp":1652820483470},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2005,5,1]],"date-time":"2005-05-01T00:00:00Z","timestamp":1114905600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2005,5]]},"DOI":"10.1007\/s10994-005-0464-5","type":"journal-article","created":{"date-parts":[[2005,6,9]],"date-time":"2005-06-09T09:02:36Z","timestamp":1118307756000},"page":"99-123","source":"Crossref","is-referenced-by-count":2,"title":["Maximizing Agreements with One-Sided Error with Applications to Heuristic Learning"],"prefix":"10.1007","volume":"59","author":[{"given":"Nader H.","family":"Bshouty","sequence":"first","affiliation":[]},{"given":"Lynn","family":"Burroughs","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1\/2","key":"464_CR1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","volume":"147","author":"E. Amaldi","year":"1995","unstructured":"Amaldi, E., & Kann, V. (1995). The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science, 147:1\/2, 181\u2013210.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"464_CR2","first-page":"343","volume":"2","author":"D. Angluin","year":"1987","unstructured":"Angluin, D., & Laird, P. D. (1987). Learning from noisy examples. Machine Learning, 2:4, 343\u2013370.","journal-title":"Machine Learning"},{"key":"464_CR3","doi-asserted-by":"crossref","unstructured":"Bartlett, P. L., & Ben-David, S. (1999). Hardness results for neural network approximation problems. In Proceedings of the 4th European Conference on Computational Learning Theory (pp. 50\u201362).","DOI":"10.1007\/3-540-49097-3_5"},{"issue":"3","key":"464_CR4","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1016\/S0022-0000(03)00038-2","volume":"66","author":"S. Ben-David","year":"2003","unstructured":"Ben-David, S., Eiron, N., & Long, P. M. (2003). On the difficulty of approximately maximizing agreements. Journal of Computer and System Sciences, 66:3, 496\u2013514.","journal-title":"Journal of Computer and System Sciences"},{"key":"464_CR5","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 26th Annual ACM Symposium on Theory of Computing (pp. 253\u2013262).","DOI":"10.1145\/195058.195147"},{"key":"464_CR6","unstructured":"Blum, A. L., & Rivest, R. L. (1988). Training a 3-node neural network is NP-complete. In Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 9\u201318)."},{"issue":"6","key":"464_CR7","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"24","author":"A. Blumer","year":"1987","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987). Occam\u2019s razor. Information Processing Letters, 24:6, 377\u2013380.","journal-title":"Information Processing Letters"},{"key":"464_CR8","doi-asserted-by":"crossref","unstructured":"Bshouty, N. H., & Burroughs, L. (2002a). Bounds for the minimum disagreement problem with applications to learning theory. In Proceedings of the 15th Annual Conference on Computational Learning Theory (pp. 271\u2013286).","DOI":"10.1007\/3-540-45435-7_19"},{"key":"464_CR9","doi-asserted-by":"crossref","unstructured":"Bshouty, N. H., & Burroughs, L. (2002b). Maximizing agreements and coagnostic learning. In Proceedings of the 13th International Conference on Algorithmic Learning Theory.","DOI":"10.1007\/3-540-36169-3_9"},{"key":"464_CR10","unstructured":"H\u00e5stad, J. (1996). Clique is hard to approximate within n1\u2212\u03b5. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (pp. 627\u2013636)."},{"key":"464_CR11","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J. (1997). Some optimal inapproximability results. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (pp. 1\u201310).","DOI":"10.1145\/258533.258536"},{"issue":"1","key":"464_CR12","first-page":"114","volume":"50","author":"K.-U. H\u00f6ffgen","year":"1995","unstructured":"H\u00f6ffgen, K.-U., Simon, H.-U., & Van Horn, K. S. (1995). Robust trainability of single neurons, JCSS, 50:1, 114\u2013125.","journal-title":"JCSS"},{"issue":"4","key":"464_CR13","first-page":"606","volume":"E83-A","author":"T. Itoh","year":"2000","unstructured":"Itoh, T. (2000). Approximating the maximum weight of linear codes is APX-complete. On Fundamentals of Electronics, Communications and Computer Sciences, E83-A:4, 606\u2013613.","journal-title":"On Fundamentals of Electronics, Communications and Computer Sciences"},{"key":"464_CR14","unstructured":"Kann, V., Khanna, S., Lagergren, J., & Panconesi, A. (1996). On the hardness of approximating max-k-cut and its dual. In Proceedings of the Fourth Israeli Symposium on Theory of Computing and Systems (pp. 61\u201367)."},{"issue":"4","key":"464_CR15","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1137\/0222052","volume":"22","author":"M. Kearns","year":"1993","unstructured":"Kearns, M., & Li, M. (1993). Learning in the presence of malicious errors. SIAM Journal on Computing, 22:4, 807\u2013837.","journal-title":"SIAM Journal on Computing"},{"key":"464_CR16","unstructured":"Kuhlmann, C. (2000). Hardness results for general two-layer neural networks. In Proceedings of the 13th Annual Conference on Computational Learning Theory (pp. 275\u2013285)."},{"issue":"1","key":"464_CR17","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0304-3975(93)90259-V","volume":"107","author":"A. Panconesi","year":"1993","unstructured":"Panconesi, A., & Ranjan, D. (1993). Quantifiers and approximation. Theoretical Computer Science, 107:1, 145\u2013163.","journal-title":"Theoretical Computer Science"},{"key":"464_CR18","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., & Yannakakis, M. (1991). Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43, 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"464_CR19","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L., & Valiant, L. G. (1988). Computational limitations on learning from examples. JACM, 35:4, 965\u2013984.","journal-title":"JACM"},{"issue":"11","key":"464_CR20","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27:11, 1134\u20131142.","journal-title":"Communications of the ACM"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-005-0464-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-005-0464-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-005-0464-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T01:40:18Z","timestamp":1559353218000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-005-0464-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5]]},"references-count":20,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2005,5]]}},"alternative-id":["464"],"URL":"https:\/\/doi.org\/10.1007\/s10994-005-0464-5","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5]]}}}