{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T19:15:11Z","timestamp":1791054911306,"version":"4.1.0"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>Given a function f mapping n-variate inputs from a finite field F into F, we consider the task of reconstructing a list of all n-variate degree d polynomials that agree with f on a tiny but nonnegligible fraction, $\\delta$, of the input space. We give a randomized algorithm for solving this task. The algorithm accesses f as a black box and runs in time polynomial in ${\\frac{n}\\d}$ and exponential in d, provided $\\delta$ is $\\Omega(\\sqrt{d\/|F|})$. For the special case when d = 1, we solve this problem for all $\\epsilon\\eqdef\\delta - \\frac1{|F|} &gt;0$. In this case the running time of our algorithm is bounded by a polynomial in $\\frac1\\e$ and n. Our algorithm generalizes a previously known algorithm, due to Goldreich and Levin [in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, ACM Press, New York, 1989, pp. 25--32.], that solves this task for the case when F = GF(2) (and d = 1).<\/jats:p>\n                  <jats:p>In the process we provide new bounds on the number of degree d polynomials that may agree with any given function on $\\d \\geq \\sqrt{d\/|F|}$ fraction of the inputs. This result is derived by generalizing a well-known bound from coding theory on the number of codewords from an error-correcting code that can be \"close\" to an arbitrary word; our generalization works for codes over arbitrary alphabets, while the previous result held only for binary alphabets.<\/jats:p>","DOI":"10.1137\/s0895480198344540","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"535-570","source":"Crossref","is-referenced-by-count":75,"title":["Learning Polynomials with Queries: The Highly Noisy Case"],"prefix":"10.1137","volume":"13","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116829"},{"key":"R2","unstructured":"D. Angluin and M. Kri\u0137is,\n                      Learning with malicious membership queries and exceptions\n                      , in Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, New Brunswick, NJ, ACM Press, New York, 1994, pp. 57\u201366."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796297577"},{"key":"R4","unstructured":"S. Arora and M. Sudan,\n                      Improved low degree testing and its applications\n                      , in Proceedingsof the 29th Annual ACM Symposium on Theory of Computing, El Paso, TX, 1997, ACM Press, New York, pp. 485\u2013495."},{"key":"R5","unstructured":"DonaldBeaver, JoanFeigenbaum, Hiding instances in multioracle queries (extended abstract), Lecture Notes in Comput. Sci., Vol. 415, Springer, Berlin, 1990, 37\u2013481063302"},{"key":"R6","unstructured":"A. Blum and P. Chalasani,\n                      Learning switching concepts\n                      , in Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, ACM Press, Pittsburgh, PA, 1992, pp. 231\u2013242."},{"key":"R7","unstructured":"AvrimBlum, MerrickFurst, MichaelKearns, RichardLipton, Cryptographic primitives based on hard learning problems, Lecture Notes in Comput. Sci., Vol. 773, Springer, Berlin, 1994, 278\u20132911288971"},{"key":"R8","unstructured":"ManuelBlum, MichaelLuby, RonittRubinfeld, Self\u2010testing\/correcting with applications to numerical problems, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), Vol. 47, 1993, 549\u201359594m:65020"},{"key":"R9","unstructured":"R. Cleve and M. Luby,\n                      A Note on Self\u2010Testing\/Correcting Methods for Trigonometric Functions\n                      , International Computer Science Institute Technical Report TR\u201090\u2010032, ICSI, Berkeley, CA, 1990."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"R11","unstructured":"P. Elias,\n                      List decoding for noisy channels\n                      , in 1957\u2010IRE WESCON Convention Record, Part 2, IRE\u2010IEEE Press, New York, 1957, pp. 94\u2013104."},{"key":"R12","unstructured":"Y. Freund and D. Ron,\n                      Learning to model sequences generated by switching distributions\n                      , in Proceedings of the Eighth Annual Conference on Computational Learning Theory, ACM Press, Santa Cruz, CA, 1995, pp. 41\u201350."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0222047"},{"key":"R14","unstructured":"P. Gemmell, R. J. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson,\n                      Self\u2010testing\/correcting for polynomials and for approximate functions\n                      , in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, LA, ACM Press, New York, 1991, pp. 32\u201342."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90195-2"},{"key":"R16","unstructured":"O. Goldreich,\n                      Foundations of Cryptography\u2014Fragments of a Book\n                      , Weizmann Institute of Science, Rehovot, Israel, 1995."},{"key":"R16","unstructured":"Available from theECCC, http:\/\/www.eccc.uni\u2010trier.de\/eccc\/."},{"key":"R17","unstructured":"O. Goldreich and L. A. Levin,\n                      A hard\u2010core predicate for all one\u2010way functions\n                      , in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, ACM Press, New York, 1989, pp. 25\u201332."},{"key":"R18","unstructured":"OdedGoldreich, RonittRubinfeld, MadhuSudan, Learning polynomials with queries: the highly noisy case, IEEE Comput. Soc. Press, Los Alamitos, CA, 1995, 294\u20133031619091"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0222052"},{"key":"R22","unstructured":"M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. E. Schapire, and L. Sellie,\n                      On the learnability of discrete distributions (extended abstract)\n                      , in Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, Montreal, Canada, ACM Press, New York, 1994, pp. 273\u2013282."},{"key":"R23","unstructured":"M. J. Kearns, R. E. Schapire, and L. M. Sellie,\n                      Toward efficient agnostic learning (extended abstract)\n                      , in Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, Pittsburgh, PA, ACM Press, New York, 1992."},{"key":"R24","unstructured":"P. Koiran,\n                      Efficient learning of continuous neural networks\n                      , in Proceedings of the 7th Annual ACM Conference on Computational Learning Theory, New Brunswick, NJ, ACM Press, New York, 1994, pp.348\u2013355."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"R26","unstructured":"P. D. Laird,\n                      Learning From Good and Bad Data\n                      , Kluwer Academic Publishers, Boston, 1988."},{"key":"R27","first-page":"1102","volume":"58","author":"Levin L. A.","year":"1993","journal-title":"J. Symbolic Logic","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4812","issn-type":"print"},{"key":"R28","unstructured":"RichardLipton, New directions in testing, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 2, Amer. Math. Soc., Providence, RI, 1991, 191\u201320292c:68127"},{"key":"R29","unstructured":"W. Maass,\n                      Efficient agnostic PAC\u2010learning with simple hypotheses\n                      , in Proceedings of the 7th Annual ACM Conference on Computational Learning Theory, New Brunswick, NJ, ACM Press, New York, 1994, pp. 67\u201375."},{"key":"R30","unstructured":"W. Maass,\n                      Agnostic PAC\u2010learning of functions on analog neural nets\n                      , in Proceedings of the 6th Conference on Advances in Neural Information Processing Systems, J. D. Cowan, G. Tesauro, and J. Alspector, eds., Morgan Kaufmann, San Mateo, CA, 1994, pp. 311\u2013318."},{"key":"R31","first-page":"137","author":"Uehara Tsuyoshi","year":"1998","journal-title":"S\u016brikaisekikenky\u016bsho K\u014dky\u016broku"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792239291"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993409"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298625"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90220-C"},{"key":"R37","unstructured":"Y. Sakakibara and R. Siromoney,\n                      A noise model on learning sets of strings\n                      , in Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, ACM Press, Pittsburgh, PA, ACM Press, New York, 1992, pp. 295\u2013302."},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"R39","unstructured":"RobertSloan, Types of noise in data for concept learning (extended abstract), Morgan Kaufmann, San Mateo, CA, 1989, 91\u2013961109726"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"R41","unstructured":"M. Sudan, L. Trevisan, and S. Vadhan,\n                      Pseudorandom generators without the XOR lemma\n                      , in Proceedings of the 31st Annual ACM Symposium on Theory of Computing, Atlanta, GA, ACM Press, New York, 1999, pp. 537\u2013546."},{"key":"R42","unstructured":"L. G. Valiant,\n                      Learning disjunctions of conjunctions\n                      , in Proceedings of the 9th International Joint Conference on Artificial Intelligence, Los Angeles, 1985, Morgan Kauffman Publishers, San Mateo, CA, 1985, pp. 560\u2013566."},{"key":"R43","unstructured":"U. V. Vazirani and V. V. Vazirani,\n                      Efficient and secure pseudo\u2010random number generation\n                      , in Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, Singer Island, FL, 1984, IEEE, New York, 1984, pp. 458\u2013463."},{"key":"R44","unstructured":"HalWasserman, Reconstructing randomly sampled multivariate polynomials from highly noisy data, ACM, New York, 1998, 59\u20136799h:68087"},{"key":"R45","unstructured":"L. R. Welch and E. R. Berlekamp,\n                      Error Correction of Algebraic Block Codes\n                      , US patent 4,633,470, December 30, 1986."},{"key":"R46","unstructured":"RichardZippel, Probabilistic algorithms for sparse polynomials, Lecture Notes in Comput. Sci., Vol. 72, Springer, Berlin, 1979, 216\u201322681g:68061"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80018-1"},{"key":"R48","unstructured":"R. E. Zippel,\n                      Effective Polynomial Computation\n                      , Kluwer Academic Publishers, Boston, 1993."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480198344540","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:53:56Z","timestamp":1787320436000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480198344540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S0895480198344540"],"URL":"https:\/\/doi.org\/10.1137\/s0895480198344540","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}