{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T02:04:14Z","timestamp":1760061854933},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1996,9,1]],"date-time":"1996-09-01T00:00:00Z","timestamp":841536000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[1996,9]]},"DOI":"10.1007\/bf01293594","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T22:09:21Z","timestamp":1111702161000},"page":"351-364","source":"Crossref","is-referenced-by-count":10,"title":["Sparse shifts for univariate polynomials"],"prefix":"10.1007","volume":"7","author":[{"given":"Y. N.","family":"Lakshman","sequence":"first","affiliation":[]},{"given":"B. David","family":"Saunders","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"Ben Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. Proc. 20th Symp. Theory Comput. ACM Press, pp. 301?309 (1988)","DOI":"10.1145\/62212.62241"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"Borodin, A., Tiwari, P.: On the decidability of sparse univariate polynomial interpolation. Proc. 22nd Symp. Theory Comput. ACM Press, pp. 535?545 (1990)","DOI":"10.1145\/100216.100292"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1215\/ijm\/1256053748","volume":"13","author":"M. D. Fried","year":"1969","unstructured":"Fried, M. D., MacRae, R. E.: On the invariance of chains of fields. Ill. J. Math.,13, 165?171 (1969)","journal-title":"Ill. J. Math."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"von zur Gathen, J., Kozen, D., Landau, S.: Functional decomposition of polynomials. Proc. 28th IEEE Symp. Found. Comp. Sci., pp. 127?131. Nov 1987","DOI":"10.1109\/SFCS.1987.29"},{"key":"CR5","unstructured":"Clausen, M., Dress, A., Grabmeier, J., Karpinski, M: On zero testing and interpolation ofk-sparse multivariate polynomials over finite fields. TR 88.06.006, IBM Germany, Heidelberg Scientific Center. June 1988"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"Grigoriev, D. Yu., Karpinski, M.: The matching problem for bipartite graphs with polynomially bounded permanents is in NC. Proc. 28th IEEE Symp. Foundations Comp. Sci. pp. 166?172 (1987)","DOI":"10.1109\/SFCS.1987.56"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1137\/0219073","volume":"19","author":"D. Grigoriev","year":"1990","unstructured":"Grigoriev, D., Karpinski, M., Singer, M.: Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. SIAM J. Comp.19, 1059?1063 (1990)","journal-title":"SIAM J. Comp."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539791194069","volume":"23","author":"D. Grigoriev","year":"1994","unstructured":"Grigoriev, D., Karpinski, M., Singer, M.: Computational complexity of sparse rational interpolations. SIAM J. Comp.23, 1?11 (1994)","journal-title":"SIAM J. Comp."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M., Singer, M.: Computational complexity of sparse real algebraic function interpolation. Proc. MEGA '92, Progress in Mathematics, Birkhauser, Basel Vol. 109, pp. 91?104","DOI":"10.1007\/978-1-4612-2752-6_7"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0196-8858(91)90005-4","volume":"12","author":"D. Grigoriev","year":"1991","unstructured":"Grigoriev, D., Karpinski, M., Singer, M.: The interpolation problem for k-sparse sums of eigenfunctions of operators. Adv Appl Math12, 76?81 (1991)","journal-title":"Adv Appl Math"},{"key":"CR11","series-title":"Lect. Notes in Comp. Sci., Vol. 673","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-56686-4_41","volume-title":"Proc. AAECC-93","author":"D. Grigoriev","year":"1993","unstructured":"Grigoriev, D., Karpinski, M.: A zero-test and an interpolation algorithm for the shifted sparse polynomials. Proc. AAECC-93, Lect. Notes in Comp. Sci., Vol. 673, pp. 162?169. Berlin, Heidelberg, New York, Springer 1993"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M., Odlyzko, A. M.: Existence of short proofs of non-divisibility of sparse polynomials under the extended Riemann hypothesis. Proc. ISSAC 92, ACM Press, pp. 117?122 (1992a)","DOI":"10.1145\/143242.143287"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"Kaltofen, E.: Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials. Proc. 19th Symp. Theory of Computing, ACM Press, pp. 443?452 (1987)","DOI":"10.1145\/28395.28443"},{"key":"CR14","first-page":"167","volume-title":"Proc. ISSAC 1988","author":"E. Kaltofen","year":"1988","unstructured":"Kaltofen, E., Lakshman, Y. N.: Improved sparse multivariate polynomial interpolation algorithms, Proc. ISSAC 1988, Rome, Italy, Berlin, Heidelberg, New york. Springer LNCS vol. 358, pp. 167?474 (1988)"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0747-7171(08)80015-6","volume":"9","author":"E. Kaltofen","year":"1990","unstructured":"Kaltofen, E., Trager, B.: Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators. J. Symb. Comp.9, 301?320 (1990)","journal-title":"J. Symb. Comp."},{"key":"CR16","unstructured":"Kaplanski, I.: An introduction to differential algebra. Hermann, Paris."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"Kozen, D., Landau, S.: Polynomial decomposition algorithms. JSC, Vol. 7, (5), 445?456","DOI":"10.1016\/S0747-7171(89)80027-6"},{"issue":"2","key":"CR18","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1137\/S0097539792237784","volume":"24","author":"Y. N. Lakshman","year":"1995","unstructured":"Lakshman, Y. N., Saunders, B. D.: Sparse polynomial interpolation in non-standard bases. SIAM J. Comp.24, (2), 387?397 (1995)","journal-title":"SIAM J. Comp."},{"key":"CR19","volume-title":"Proc. ISSAC","author":"Y. N. Lakshman","year":"1994","unstructured":"Lakshman, Y. N., Saunders, B. D.: On computing sparse shifts for univariate polynomials. Proc. ISSAC 1994, Oxford, OK, ACM Press"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"Loos, R.: Computing rational zeros of integral polynomials byp-adic expansion. SIAM J. Comp.,12, 286?293","DOI":"10.1137\/0212017"},{"issue":"2","key":"CR21","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1137\/S0097539792239291","volume":"24","author":"Y. Mansour","year":"1995","unstructured":"Mansour, Y.: Randomized interpolation and approximation of sparse polynomials. SIAM J. Comp.,24, (2), 357?368 (1995)","journal-title":"SIAM J. Comp."},{"key":"CR22","volume-title":"A treatise on the theory of determinants","author":"T. Muir","year":"1960","unstructured":"Muir, T. (enlarged by Metzler, H.): A treatise on the theory of determinants, Dover Publishing, New York (1960)"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1090\/S0002-9947-1922-1501189-9","volume":"23","author":"J. F. Ritt","year":"1922","unstructured":"Ritt, J. F.: Prime and composite polynomials. Trans. Am. Math. Soc.23, 51?66 (1922)","journal-title":"Trans. Am. Math. Soc."},{"issue":"3","key":"CR24","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","volume":"9","author":"R. Zippel","year":"1990","unstructured":"Zippel, R.: Interpolating polynomials from their values. J. Symb. Comp.,9, (3), 375?403 (1990)","journal-title":"J. Symb. Comp."}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293594.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01293594\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01293594","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:35:59Z","timestamp":1586180159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01293594"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["BF01293594"],"URL":"https:\/\/doi.org\/10.1007\/bf01293594","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}