{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T20:13:21Z","timestamp":1780085601137,"version":"3.54.0"},"reference-count":30,"publisher":"Elsevier BV","issue":"3-4","license":[{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3607,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Symbolic Computation"],"published-print":{"date-parts":[[2003,9]]},"DOI":"10.1016\/s0747-7171(03)00088-9","type":"journal-article","created":{"date-parts":[[2003,7,16]],"date-time":"2003-07-16T16:18:16Z","timestamp":1058372296000},"page":"365-400","source":"Crossref","is-referenced-by-count":85,"title":["Early termination in sparse interpolation algorithms"],"prefix":"10.1016","volume":"36","author":[{"given":"Erich","family":"Kaltofen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wen-shin","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0747-7171(03)00088-9_B1","series-title":"Proc. Twentieth Annual ACM Symp. Theory Comput.","first-page":"301","article-title":"A deterministic algorithm for sparse multivariate polynomial interpolation","author":"Ben-Or","year":"1988"},{"issue":"4","key":"10.1016\/S0747-7171(03)00088-9_B2","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1109\/TASSP.1985.1164645","article-title":"A generalization of the Levinson algorithm for Hermitian Toeplitz matrices with any rank profile","volume":"assp-33","author":"Delsarte","year":"1985","journal-title":"IEEE Trans. Acoustics Speech Signal Process"},{"issue":"4","key":"10.1016\/S0747-7171(03)00088-9_B3","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","article-title":"A probabilistic remark on algebraic program testing","volume":"7","author":"DeMillo","year":"1978","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0747-7171(03)00088-9_B4","series-title":"ISSAC\u201998, Proc. 1998 Internat. Symp. Symbolic Algebraic Comput.","first-page":"30","article-title":"FoxBox a system for manipulating symbolic objects in black box representation","author":"D\u0131\u0301az","year":"1998"},{"key":"10.1016\/S0747-7171(03)00088-9_B5","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-8858(91)90004-3","article-title":"The interpolation problem for k-sparse polynomial and character sums","volume":"12","author":"Dress","year":"1991","journal-title":"Adv. Appl. Math."},{"issue":"2","key":"10.1016\/S0747-7171(03)00088-9_B6","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1142\/S0218195998000126","article-title":"A complete implementation for computing general dimensional convex hulls","volume":"8","author":"Emiris","year":"1998","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"10.1016\/S0747-7171(03)00088-9_B7","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/44128.214376","article-title":"Dagwood A system for manipulating polynomials given by straight-line programs","volume":"14","author":"Freeman","year":"1988","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/S0747-7171(03)00088-9_B8","volume":"vol. 1","author":"Gantmacher","year":"1977"},{"key":"10.1016\/S0747-7171(03)00088-9_B9","doi-asserted-by":"crossref","DOI":"10.1016\/S0747-7171(03)00087-7","article-title":"Algorithms for computing sparsest shifts of polynomials in power, Chebychev, and Pochhammer bases","author":"Giesbrecht","year":"2003","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/S0747-7171(03)00088-9_B10","series-title":"ISSAC\u201902, Proc. 2002 Internat. Symp. Symbolic Algebraic Comput.","first-page":"101","article-title":"Algorithms for computing the sparsest shifts for polynomials via the Berlekamp\/Massey algorithm","author":"Giesbrecht","year":"2002"},{"key":"10.1016\/S0747-7171(03)00088-9_B11","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/BF01199761","article-title":"Efficient algorithm for Toeplitz plus Hankel matrices","volume":"12","author":"Gohberg","year":"1989","journal-title":"Integral Equations Operator Theory"},{"issue":"6","key":"10.1016\/S0747-7171(03)00088-9_B12","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1137\/0219073","article-title":"Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields","volume":"19","author":"Grigoriev","year":"1990","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0747-7171(03)00088-9_B13","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0196-8858(91)90005-4","article-title":"The interpolation problem for k-sparse sums of eigenfunctions of operators","volume":"12","author":"Grigoriev","year":"1991","journal-title":"Adv. Appl. Math."},{"key":"10.1016\/S0747-7171(03)00088-9_B14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539791194069","article-title":"Computational complexity of sparse rational function interpolation","volume":"23","author":"Grigoriev","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0747-7171(03)00088-9_B15","series-title":"An Introduction to the Theory of Numbers","author":"Hardy","year":"1979"},{"key":"10.1016\/S0747-7171(03)00088-9_B16","series-title":"ISSAC\u201990, Proc. 1990 Internat. Symp. Symbolic Algebraic Comput.","first-page":"135","article-title":"Modular rational sparse multivariate polynomial interpolation","author":"Kaltofen","year":"1990"},{"key":"10.1016\/S0747-7171(03)00088-9_B17","series-title":"Symbolic Algebraic Comput. Internat. Symp. ISSAC\u201988 Proc.","first-page":"467","article-title":"Improved sparse multivariate polynomial interpolation algorithms","volume":"vol. 358","author":"Kaltofen","year":"1988"},{"key":"10.1016\/S0747-7171(03)00088-9_B18","series-title":"ISSAC\u201900, Proc. 2000 Internat. Symp. Symbolic Algebraic Comput.","first-page":"192","article-title":"Early termination in Ben-Or\/Tiwari sparse interpolation and a hybrid of Zippel\u2019s algorithm","author":"Kaltofen","year":"2000"},{"key":"10.1016\/S0747-7171(03)00088-9_B19","series-title":"ISSAC\u201996, Proc. 1996 Internat. Symp. Symbolic Algebraic Comput.","first-page":"241","article-title":"On rank properties of Toeplitz matrices over finite fields","author":"Kaltofen","year":"1996"},{"issue":"3","key":"10.1016\/S0747-7171(03)00088-9_B20","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0747-7171(08)80015-6","article-title":"Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators","volume":"9","author":"Kaltofen","year":"1990","journal-title":"J. Symbolic Comput."},{"issue":"2","key":"10.1016\/S0747-7171(03)00088-9_B21","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1137\/S0097539792237784","article-title":"Sparse polynomial interpolation in non-standard bases","volume":"24","author":"Lakshman","year":"1995","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0747-7171(03)00088-9_B22","unstructured":"Lee, W., 2001. Early termination strategies in sparse interpolation algorithms. Ph.D. Thesis. North Carolina State University, Raleigh, North Carolina, USA, p.\u00a0107"},{"key":"10.1016\/S0747-7171(03)00088-9_B23","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1109\/TIT.1969.1054260","article-title":"Shift-register synthesis and BCH decoding","volume":"it-15","author":"Massey","year":"1969","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/S0747-7171(03)00088-9_B24","unstructured":"Prony, R., Flor\u00e9al et Prairial III (1795). Essai exp\u00e9rimental et analytique sur les lois de la Dilatabilit\u00e9 des fluides \u00e9lastiques et sur celles de la Force expansive de la vapeur de l\u2019eau et de la vapeur de l\u2019alkool, \u00e0 diff\u00e9rentes temp\u00e9ratures. J. de l\u2019\u00c9cole Polytechnique 1, 24\u201376, R.\u00a0Prony is Gaspard(-Clair-Fran\u00e7ois-Marie) Riche, baron de Prony"},{"key":"10.1016\/S0747-7171(03)00088-9_B25","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast probabilistic algorithms for verification of polynomial identities","volume":"27","author":"Schwartz","year":"1980","journal-title":"J. ACM"},{"key":"10.1016\/S0747-7171(03)00088-9_B26","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","article-title":"Solving sparse linear equations over finite fields","volume":"it 32","author":"Wiedemann","year":"1986","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/S0747-7171(03)00088-9_B27","series-title":"ISSAC 99, Proc. 1999 Internat. Symp. Symbolic Algebraic Comput.","first-page":"67","article-title":"On feasible multivariate polynomial interpolations over arbitrary fields","author":"Zilic","year":"1999"},{"key":"10.1016\/S0747-7171(03)00088-9_B28","series-title":"Proc. EUROSAM\u00a0\u201979","first-page":"216","article-title":"Probabilistic algorithms for sparse polynomials","volume":"vol. 72","author":"Zippel","year":"1979"},{"key":"10.1016\/S0747-7171(03)00088-9_B29","doi-asserted-by":"crossref","unstructured":"Zippel, R.E., 1979b. Probabilistic algorithms for sparse polynomials. Ph.D. Thesis. Massachusetts Institute of Technology, Cambridge, USA","DOI":"10.1007\/3-540-09519-5_73"},{"issue":"3","key":"10.1016\/S0747-7171(03)00088-9_B30","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","article-title":"Interpolating polynomials from their values","volume":"9","author":"Zippel","year":"1990","journal-title":"J. Symbolic Comput."}],"container-title":["Journal of Symbolic Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717103000889?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717103000889?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T18:26:44Z","timestamp":1585074404000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0747717103000889"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,9]]},"references-count":30,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2003,9]]}},"alternative-id":["S0747717103000889"],"URL":"https:\/\/doi.org\/10.1016\/s0747-7171(03)00088-9","relation":{},"ISSN":["0747-7171"],"issn-type":[{"value":"0747-7171","type":"print"}],"subject":[],"published":{"date-parts":[[2003,9]]}}}