{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T07:10:44Z","timestamp":1791270644388,"version":"4.1.0"},"reference-count":75,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>We study the learnability of several fundamental concept classes in the agnostic learning framework of [D. Haussler, Inform. and Comput., 100 (1992), pp. 78\u2013150] and [M. Kearns, R. Schapire, and L. Sellie, Machine Learning, 17 (1994), pp. 115\u2013141]. We show that under the uniform distribution, agnostically learning parities reduce to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of [A. Blum, A. Kalai, and H. Wasserman, J. ACM, 50 (2003), pp. 506\u2013519], this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of disjunctive normal form (DNF) expressions reduces to learning noisy parities of just logarithmic number of variables, and learning of k-juntas reduces to learning noisy parities of k variables. We give essentially optimal hardness results for agnostic learning of monomials over $\\{0,1\\}^n$ and halfspaces over $\\mathbb{Q}^n$. We show that for any constant $\\epsilon$ finding a monomial (halfspace) that agrees with an unknown function on $1\/2+\\epsilon$ fraction of the examples is NP-hard even when there exists a monomial (halfspace) that agrees with the unknown function on $1-\\epsilon$ fraction of the examples. This resolves an open question due to Blum and significantly improves on a number of previous hardness results for these problems. We extend these results to $\\epsilon=2^{-\\log^{1-\\lambda}n}$ ($\\epsilon=2^{-\\sqrt{\\log n}}$ in the case of halfspaces) for any constant $\\lambda&gt;0$ under stronger complexity assumptions.<\/jats:p>","DOI":"10.1137\/070684914","type":"journal-article","created":{"date-parts":[[2009,7,23]],"date-time":"2009-07-23T18:02:05Z","timestamp":1248372125000},"page":"606-645","source":"Crossref","is-referenced-by-count":37,"title":["On Agnostic Learning of Parities, Monomials, and Halfspaces"],"prefix":"10.1137","volume":"39","author":[{"given":"Vitaly","family":"Feldman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Parikshit","family":"Gopalan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhash","family":"Khot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashok Kumar","family":"Ponnuswami","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,7,23]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-037-2"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Ajtai and C. Dwork,\n                      A public-key cryptosystem with worst-case\/average-case equivalence\n                      , in Proceedings of the 29th ACM Symposium on the Theory of Computing, ACM, New York, 1997, pp. 284\u2013293.","DOI":"10.1145\/258533.258604"},{"key":"R3","unstructured":"E. Amaldi,\n                      From Finding Feasible Subsystems of Linear Systems to Feedforward Neural Network Design\n                      , Ph.D. Thesis, Swiss Federal Institute of Technology at Lausanne (EPFL), Lausanne, Switzerland, 1994."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00254-G"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116829"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"J. Aspnes, R. Beigel, M. Furst, and S. Rudich,\n                      The expressive power of voting polynomials\n                      , in Proceedings of the 23rd ACM Symposium on Theory of Computing, ACM, New York, 1991, pp. 402\u2013409.","DOI":"10.1145\/103418.103461"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"R. Beigel, N. Reingold, and D. A. Spielman,\n                      The perceptron strikes back\n                      , in Proceedings of the 6th Annual Conference on Structure in Complexity Theory, IEEE Computer Society Press, Piscataway, NJ, 1991, pp. 286\u2013291.","DOI":"10.1109\/SCT.1991.160270"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00038-2"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055873"},{"key":"R13","unstructured":"A. Blum,\n                      Relevant examples and relevant features: Thoughts from computational learning theory\n                      , in AAAI Fall Symposium on `Relevance,' 1994, pp. 245\u2013272."},{"key":"R14","unstructured":"A. Blum,\n                      Lecture Notes for\n                      15-854\n                      Machine Learning Theory\n                      , available online at http:\/\/www.cs.cmu.edu\/~avrim\/ML98\/index.html, 1998."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. Blum,\n                      \n                        Open problem: Learning a function of\n                        r\n                        relevant variables\n                      \n                      , in Proceeding of the 16th Annual Conference on Learning Theory (COLT), 2003, pp. 731\u2013733.","DOI":"10.1007\/978-3-540-45167-9_54"},{"key":"R16","unstructured":"A. Blum,\n                      Tutorial on Machine Learning Theory given at FOCS\n                      '03, available online at http:\/\/www.cs.cmu.edu\/~avrim\/Talks\/FOCS03\/, 2003."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013833"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Blum, M. Furst, M. Kearns, and R. J. Lipton,\n                      Cryptographic primitives based on hard learning problems\n                      , in Proceedings of the International Cryptology Conference on Advances in Cryptology (CRYPTO), 1993, pp. 278\u2013291.","DOI":"10.1007\/3-540-48329-2_24"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792543"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00063-5"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90114-1"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.014"},{"key":"R23","first-page":"359","volume":"2","author":"Bshouty N.","year":"2002","journal-title":"J. Machine Learning Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.10.002"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"E. Cohen,\n                      Learning noisy perceptrons by a perceptron in polynomial time\n                      , in Proceedings of the 38th IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 1997, pp. 514\u2013523.","DOI":"10.1109\/SFCS.1997.646140"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.806118"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"V. Feldman,\n                      Optimal hardness results for maximizing agreements with monomials\n                      , in Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC), IEEE Computer Society Press, Piscataway, NJ, 2006, pp. 226\u2013236.","DOI":"10.1109\/CCC.2006.31"},{"key":"R29","first-page":"1431","volume":"8","author":"Feldman V.","year":"2007","journal-title":"J. Machine Learning Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"V. Feldman, P. Gopalan, S. Khot, and A. Ponuswami,\n                      New results for learning noisy parities and halfspaces\n                      , in Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2006, pp. 563\u2013574.","DOI":"10.1109\/FOCS.2006.51"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Y. Freund,\n                      An improved boosting algorithm and its implications on learning complexity\n                      , in Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, ACM, New York, 1992, pp. 391\u2013398.","DOI":"10.1145\/130385.130429"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1136"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1109\/72.80230"},{"key":"R34","unstructured":"M. Garey and D. S. Johnson,\n                      Computers and Intractability\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1723"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. Levin,\n                      A hard-core predicate for all one-way functions\n                      , in Proceedings of the 21st ACM Symposium on the Theory of Computing, ACM, New York, 1989, pp. 25\u201332.","DOI":"10.1145\/73007.73010"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"V. Guruswami and P. Raghavendra,\n                      Hardness of learning halfspaces with noise\n                      , in Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2006, pp. 543\u2013552.","DOI":"10.1109\/FOCS.2006.33"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"V. Guruswami and P. Raghavendra,\n                      A 3-query pcp over integers\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 198\u2013206.","DOI":"10.1145\/1250790.1250819"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90001-D"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"R41","unstructured":"D. Haussler,\n                      Space Efficient Learning Algorithms\n                      , Technical Report UCSC-CRL-88-2, University of California at Santa Cruz, Santa Cruz, CA, 1988."},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1137\/0221019"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1011"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00401-8"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1533"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"J. Jackson, E. Shamir, and C. Shwartzman,\n                      Learning with queries corrupted by classification noise\n                      , in Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems, 1997, pp. 45\u201353.","DOI":"10.1109\/ISTCS.1997.595156"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90006-3"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"A. Kalai, A. Klivans, Y. Mansour, and R. Servedio,\n                      Agnostically learning halfspaces\n                      , in Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2005, pp. 11\u201320.","DOI":"10.1109\/SFCS.2005.13"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1137\/0222052"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"M. Kearns, M. Li, L. Pitt, and L. Valiant,\n                      On the learnability of Boolean formulae\n                      , in Proceedings of the 19th ACM Symposium on the Theory of Computing, ACM, New York, 1987, pp. 285\u2013295.","DOI":"10.1145\/28395.28426"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"R54","doi-asserted-by":"crossref","unstructured":"S. Khot and A. K. Ponnuswami,\n                      Better inapproximability results for MaxClique, Chromatic Number and Min-3Lin-Deletion\n                      , in Proceedings of the 33rd International Colloquium on Automatica, Languages and Programming, EATCS, Aarhus, Denmark, 2006, pp. 226\u2013237.","DOI":"10.1007\/11786986_21"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022949332276"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"R57","doi-asserted-by":"crossref","unstructured":"A. Klivans and A. Sherstov,\n                      Cryptographic hardness for learning intersections of halfspaces\n                      , in Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2006, pp. 553\u2013562.","DOI":"10.1109\/FOCS.2006.24"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"R59","doi-asserted-by":"crossref","unstructured":"W. S. Lee, P. L. Bartlett, and R. C. Williamson,\n                      On efficient agnostic learning of linear combinations of basis functions\n                      , in Proceedings of the 8th Annual Conference on Computational Learning Theory (COLT), 1995, pp. 369\u2013376.","DOI":"10.1145\/225298.225343"},{"key":"R60","first-page":"1102","volume":"58","author":"Levin L.","year":"1993","journal-title":"J. Symbolic Logic","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4812","issn-type":"print"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"R63","unstructured":"M. Luby and A. Wigderson,\n                      Pairwise Independence and Derandomization\n                      , Technical Report 95-035, International Computer Science Institute, Berkeley, CA, 1995."},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"R65","unstructured":"R. J. McEliece,\n                      A public-key cryptosystem based on algebraic coding theory\n                      , DSN Progress Report, 1978, pp. 42\u201344."},{"key":"R66","unstructured":"M. Minsky and S. Papert,\n                      Perceptrons: An Introduction to Computational Geometry\n                      , MIT Press, Cambridge, MA, 1969."},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.002"},{"key":"R68","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R69","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"R70","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra,\n                      A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP\n                      , in Proceedings of the 29th ACM Symposium on the Theory of Computing, ACM, New York, 1997, pp. 475\u2013484.","DOI":"10.1145\/258533.258641"},{"key":"R71","unstructured":"F. Rosenblatt,\n                      Principles of Neurodynamics\n                      , Spartan Books, New York, 1962."},{"key":"R72","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116037"},{"key":"R73","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"R74","unstructured":"L. G. Valiant,\n                      Learning disjunctions of conjunctions\n                      , in Proceedings of the 9th International Joint Conference on Artificial Intelligence, 1985, pp. 560\u2013566."},{"key":"R75","doi-asserted-by":"crossref","unstructured":"K. Verbeurgt,\n                      Learning DNF under the uniform distribution in quasi-polynomial time\n                      , in Proceedings of the 3rd Annual Workshop on Computational Learning Theory, 1990, pp. 314\u2013326.","DOI":"10.1016\/B978-1-55860-146-8.50027-8"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070684914","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:38Z","timestamp":1787337218000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070684914"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":75,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/070684914"],"URL":"https:\/\/doi.org\/10.1137\/070684914","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}