{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T18:22:14Z","timestamp":1775672534528,"version":"3.50.1"},"reference-count":24,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T00:00:00Z","timestamp":1051747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3766,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,5]]},"DOI":"10.1016\/s0022-0000(03)00038-2","type":"journal-article","created":{"date-parts":[[2003,5,13]],"date-time":"2003-05-13T01:09:12Z","timestamp":1052788152000},"page":"496-514","source":"Crossref","is-referenced-by-count":58,"title":["On the difficulty of approximately maximizing agreements"],"prefix":"10.1016","volume":"66","author":[{"given":"Shai","family":"Ben-David","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadav","family":"Eiron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip M.","family":"Long","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00038-2_BIB1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","article-title":"The complexity and approximability of finding maximum feasible subsystems of linear relations","volume":"147","author":"Amaldi","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00038-2_BIB2","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF00116829","article-title":"Learning from noisy examples","volume":"2","author":"Angluin","year":"1988","journal-title":"Mach. Learning"},{"issue":"2","key":"10.1016\/S0022-0000(03)00038-2_BIB3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1006\/jcss.1997.1472","article-title":"Hardness of approximate optima in lattices, codes, and linear systems","volume":"54","author":"Arora","year":"1997","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00038-2_BIB4","doi-asserted-by":"crossref","unstructured":"P. Bartlett, S. Ben-David, Hardness results for neural network approximation problems, The 1999 IMA European Conference on Computational Learning Theory, 1999, pp. 50\u201362.","DOI":"10.1007\/3-540-49097-3_5"},{"key":"10.1016\/S0022-0000(03)00038-2_BIB5","unstructured":"S. Ben-David, N. Eiron, H.U. Simon, On the hardness of unsupervised learning, 2000, to appear."},{"issue":"1","key":"10.1016\/S0022-0000(03)00038-2_BIB6","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0893-6080(05)80010-3","article-title":"Training a 3-node neural network is NP-complete","volume":"5","author":"Blum","year":"1992","journal-title":"Neural Networks"},{"issue":"4","key":"10.1016\/S0022-0000(03)00038-2_BIB7","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","article-title":"Learnability and the Vapnik\u2013Chervonenkis dimension","volume":"36","author":"Blumer","year":"1989","journal-title":"J. Assoc. Comput. Mach."},{"issue":"6","key":"10.1016\/S0022-0000(03)00038-2_BIB8","doi-asserted-by":"crossref","first-page":"1490","DOI":"10.1109\/72.471360","article-title":"On the complexity of training neural networks with continuous activation functions","volume":"6","author":"DasGupta","year":"1995","journal-title":"IEEE Trans. Neural Networks"},{"issue":"3","key":"10.1016\/S0022-0000(03)00038-2_BIB9","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1006\/jcss.1996.0034","article-title":"Computing the maximum bichromatic discrepancy, with applications in computer graphics and machine learning","volume":"52","author":"Dobkin","year":"1996","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00038-2_BIB10","doi-asserted-by":"crossref","unstructured":"U. Feige, A threshold of logn for approximating set cover, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, PA, 1996, pp. 314\u2013318.","DOI":"10.1145\/237814.237977"},{"key":"10.1016\/S0022-0000(03)00038-2_BIB11","doi-asserted-by":"crossref","unstructured":"Y. Freund, R.E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, Barcelona, Spain, 1995, pp. 23\u201337.","DOI":"10.1007\/3-540-59119-2_166"},{"key":"10.1016\/S0022-0000(03)00038-2_BIB12","unstructured":"Y. Freund, R. Schapire, Experiments with a new boosting algorithm, Proceedings of the Thirteenth International Conference on Machine Learning, Bari, Italy, 1996."},{"key":"10.1016\/S0022-0000(03)00038-2_BIB13","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Some optimal inapproximability results, Proceedings of the 29th ACM Symposium on the Theory of Computing, El Paso, TX, 1997, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"issue":"1","key":"10.1016\/S0022-0000(03)00038-2_BIB14","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","article-title":"Decision theoretic generalizations of the PAC model for neural net and other learning applications","volume":"100","author":"Haussler","year":"1992","journal-title":"Inform. Comput."},{"issue":"1","key":"10.1016\/S0022-0000(03)00038-2_BIB15","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF00993161","article-title":"Tracking drifting concepts by minimizing disagreements","volume":"14","author":"Helmbold","year":"1994","journal-title":"Mach. Learning"},{"issue":"1","key":"10.1016\/S0022-0000(03)00038-2_BIB16","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1006\/jcss.1995.1011","article-title":"Robust trainability of single neurons","volume":"50","author":"H\u00f6ffgen","year":"1995","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00038-2_BIB17","series-title":"Neural Network Design and the Complexity of Learning","author":"Judd","year":"1990"},{"issue":"4","key":"10.1016\/S0022-0000(03)00038-2_BIB18","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1137\/0222052","article-title":"Learning in the presence of malicious errors","volume":"22","author":"Kearns","year":"1993","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/S0022-0000(03)00038-2_BIB19","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/174644.174647","article-title":"Cryptographic limitations on learning boolean formulae and finite automata","volume":"41","author":"Kearns","year":"1994","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(03)00038-2_BIB20","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF00993468","article-title":"Toward efficient agnostic learning","volume":"17","author":"Kearns","year":"1994","journal-title":"Mach. Learning"},{"key":"10.1016\/S0022-0000(03)00038-2_BIB21","doi-asserted-by":"crossref","unstructured":"M. Kharitonov, Cryptographic hardness of distribution specific learning, Proceedings of the 25th ACM Symposium on the Theory of Computing, San Diego, CA, 1993, pp. 372\u2013381.","DOI":"10.1145\/167088.167197"},{"key":"10.1016\/S0022-0000(03)00038-2_BIB22","unstructured":"C. Kuhlmann, Hardness results for general two-layer neural networks, Proceedings of the 2000 Conference on Computational Learning Theory, Palo Alto, CA, 2000, pp. 275\u2013285."},{"issue":"4","key":"10.1016\/S0022-0000(03)00038-2_BIB23","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","article-title":"Computational limitations on learning from examples","volume":"35","author":"Pitt","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(03)00038-2_BIB24","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF00116037","article-title":"The strength of weak learnability","volume":"5","author":"Schapire","year":"1990","journal-title":"Mach. Learning"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000382?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000382?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T21:47:59Z","timestamp":1584654479000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000382"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,5]]}},"alternative-id":["S0022000003000382"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00038-2","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}