{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:55:01Z","timestamp":1787385301514,"version":"build-2736575974"},"reference-count":41,"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":[[1998,1]]},"abstract":"<jats:p>We consider a variant of the traditional task of explicitly reconstructing algebraic functions from black box representations. In the traditional setting for such problems, one is given access to an unknown function f that is represented by a black box, or an oracle, which can be queried for the value of f at any input. Given a guarantee that this unknown function f is some nice algebraicfunction, say a polynomial in its input of degree bound d, the goal of the reconstruction problem is to explicitly determine the coefficients of the unknown polynomial. All work on polynomial interpolation, especially sparse ones, are or may be presented in such a setting. The work of Kaltofen and Trager [Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators, in Proc. 29th Ann. IEEE Symp. on Foundations of Computer Science, 1988, pp. 296--305], for instance, highlights the utility of this setting, by performing numerous manipulations on polynomials presented as black boxes.<\/jats:p>\n                  <jats:p>\n                    The variant considered in this paper differs from the traditional setting in that our black boxes represent several algebraic functions f\n                    <jats:sub>1<\/jats:sub>\n                    ,...,f\n                    <jats:sub>k<\/jats:sub>\n                    , where at each input x, the box arbitrarily chooses a subset of f\n                    <jats:sub>1<\/jats:sub>\n                    (x),...,f\n                    <jats:sub>k<\/jats:sub>\n                    (x) to output and we do not know which subset it outputs. We show how to reconstruct the functions f\n                    <jats:sub>1<\/jats:sub>\n                    ,...,f\n                    <jats:sub>k<\/jats:sub>\n                    from the black box, provided the black box outputs according to these functions \"often.\" This allows us to group the sample points into sets, such that for each set, all outputs to points in the set are from the same algebraic function. Our methods are robust in the presence of a small fraction of arbitrary errors in the black box.\n                  <\/jats:p>\n                  <jats:p>Our model and techniques can be applied in the areas of computer vision, machine learning, curve fitting and polynomial approximation, self-correcting programs, and bivariate polynomial factorization.<\/jats:p>","DOI":"10.1137\/s0097539796297577","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"487-510","source":"Crossref","is-referenced-by-count":27,"title":["Reconstructing Algebraic Functions from Mixed Data"],"prefix":"10.1137","volume":"28","author":[{"given":"Sigal","family":"Ar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard J.","family":"Lipton","sequence":"additional","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,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Donald Beaver, Joan Feigenbaum, Hiding instances in multioracle queries (extended abstract), Lecture Notes in Comput. Sci., Vol. 415, Springer, Berlin, 1990, 37\u2013481063302","DOI":"10.1007\/3-540-52282-4_30"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Ben\u2010Or,\n                      Probabilistic algorithms in finite fields\n                      , in Proc. 22nd IEEE Symposium on Foundations of Computer Science, 1981, pp. 394\u2013398.","DOI":"10.1109\/SFCS.1981.37"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Ben\u2010Or and P. Tiwari,\n                      A deterministic algorithm for sparse multivariate polynomial interpolation\n                      , in Proc. 20th ACM Symposium on Theory of Computing, 1988, pp. 301\u2013309.","DOI":"10.1145\/62212.62241"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1109\/18.490539"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Blum and P. Chalasani,\n                      Learning switching concepts\n                      , in Proc. 5th Annual ACM Workshop on Computational Learning Theory, 1992, pp. 231\u2013242.","DOI":"10.1145\/130385.130411"},{"key":"R7","unstructured":"Manuel Blum, Michael Luby, Ronitt Rubinfeld, 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":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90114-1"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90103-O"},{"key":"R10","unstructured":"J. Canny,\n                      Finding edges and lines in images\n                      , Artificial Intelligence Laboratory Report, AI\u2010TR\u2010720, MIT, Cambridge, MA, 1983."},{"key":"R11","unstructured":"D. Coppersmith, Personal communication to Ronitt Rubinfeld, Fall 1990."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Joachim von zur Gathen, Algebraic complexity theory, Annual Reviews, Palo Alto, CA, 1988, 317\u201334791a:68150","DOI":"10.1146\/annurev.cs.03.060188.001533"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson,\n                      Self\u2010testing\/correcting for polynomials and for approximate functions\n                      , in Proc. 23rd ACM Symposium on Theory of Computing, 1991, pp. 32\u201342.","DOI":"10.1145\/103418.103429"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90195-2"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. Levin,\n                      A hard\u2010core predicate for any one\u2010way function\n                      , in Proc. 21st ACM Symposium on Theory of Computing, 1989.","DOI":"10.1145\/73007.73010"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan, Learning polynomials with queries: the highly noisy case, IEEE Comput. Soc. Press, Los Alamitos, CA, 1995, 294\u20133031619091","DOI":"10.1109\/SFCS.1995.492485"},{"key":"R17","first-page":"20","volume":"137","author":"Grigoriev D.","year":"1984","journal-title":"Zap. Nauchn. Sem. Lenningradskogo Otdel. Mat. Inst. Steklov. AN SSSR"},{"key":"R18","first-page":"380","volume":"29","author":"Grigoriev D.","year":"1984","journal-title":"Soviet Math. Dokl.","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"D. Grigoriev and M. Karpinski,\n                      Algorithms for Sparse Rational Interpolation\n                      , ICSI Technical Report TR\u201091\u2010011, ICSI, Berkeley, CA, 1991.","DOI":"10.1145\/120694.120696"},{"key":"R20","unstructured":"Dima Grigoriev, Marek Karpinski, Michael Singer, Interpolation of sparse rational functions without knowing bounds on exponents, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 840\u201384692k:65015"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0219073"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-72791-7"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Erich Kaltofen, A polynomial\u2010time reduction from bivariate to univariate integral polynomial factorization, IEEE, New York, 1982, 57\u201364780381","DOI":"10.1109\/SFCS.1982.56"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"E. Kaltofen and B. Trager,\n                      Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators\n                      , in 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 296\u2013305.","DOI":"10.1109\/SFCS.1988.21946"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172769"},{"key":"R28","unstructured":"Richard Lipton, New directions in testing, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 2, Amer. Math. Soc., Providence, RI, 1991, 191\u201320292c:68127"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1098\/rspb.1980.0020"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, UK, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF00058680"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"T. J. Rivlin,\n                      An Introduction of the Approximation of Functions\n                      , Dover, New York, 1969.","DOI":"10.2307\/2004443"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Ronitt Rubinfeld, Richard Zippel, A new modular interpolation algorithm for factoring multivariate polynomials (extended abstract), Lecture Notes in Comput. Sci., Vol. 877, Springer, Berlin, 1994, 93\u201310796d:12013","DOI":"10.1007\/3-540-58691-1_47"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"B. L. Van der Waerden,\n                      Algebra\n                      , Vol. 1, Frederick Ungar Publishing Co., Inc., p. 82.","DOI":"10.1007\/978-1-4684-9999-5_1"},{"key":"R38","unstructured":"R. J. Walker,\n                      Algebraic Curves\n                      , Princeton University Press, Princeton, NJ, 1950."},{"key":"R39","unstructured":"L. Welch and E. Berlekamp,\n                      Error Correction of Algebraic Block Codes\n                      , U.S. Patent Number 4,633,470, issued December 1986."},{"key":"R40","doi-asserted-by":"crossref","unstructured":"Richard Zippel, Probabilistic algorithms for sparse polynomials, Lecture Notes in Comput. Sci., Vol. 72, Springer, Berlin, 1979, 216\u201322681g:68061","DOI":"10.1007\/3-540-09519-5_73"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80018-1"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539796297577","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:22:39Z","timestamp":1787336559000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539796297577"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539796297577"],"URL":"https:\/\/doi.org\/10.1137\/s0097539796297577","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}