{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:57Z","timestamp":1725663777541},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540566861"},{"type":"electronic","value":"9783540476306"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56686-4_41","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:24:56Z","timestamp":1330255496000},"page":"162-169","source":"Crossref","is-referenced-by-count":7,"title":["A zero-test and an interpolation algorithm for the shifted sparse polynomials"],"prefix":"10.1007","author":[{"given":"Dima","family":"Grigoriev","sequence":"first","affiliation":[]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Ben-Or, M. & Tiwari, P., A deterministic algorithm for sparse multi-variate polynomial interpolation, Proc. 20 STOC ACM, 1988, pp. 301\u2013309.","DOI":"10.1145\/62212.62241"},{"key":"13_CR2","unstructured":"Chistov, A. & Grigoriev, D., Subexponential-time solving systems of algebraic equations, Preprints LOMI E-9-83, E-10-83, Leningrad, 1983."},{"key":"13_CR3","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BFb0030287","volume":"176","author":"A. Chistov","year":"1984","unstructured":"Chistov, A. & Grigoriev, D., Complexity of quantifier elimination in the theory of algebraically closed fields, Lect. Notes Comp. Sci. 176, 1984, pp. 17\u201331.","journal-title":"Lect. Notes Comp. Sci."},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Grigoriev, D. & Karpinski, M., The matching problem for bipartite graphs with polynomially bounded permanents is in NC, Proc. 28 FOCS IEEE, 1987, pp.,166\u2013172.","DOI":"10.1109\/SFCS.1987.56"},{"issue":"N6","key":"13_CR5","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 polynimial interpolation over finite fields, SIAM J. Comput. 19, N 6, 1990, pp. 1059\u20131063.","journal-title":"SIAM J. Comput."},{"key":"13_CR6","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. Math. 12, 1991, pp. 76\u201381.","journal-title":"Adv. Appl. Math."},{"key":"13_CR7","unstructured":"Grigoriev, D., Karpinski, M. & Singer, M., Computational complexity of sparse rational interpolation, to appear in SIAM J. Comput."},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M. & Singer, M., Computational complexity of sparse real algebraic function interpolation, to appear in Proc. Int. Conf. Eff. Meth. Alg. Geom., Nice, April 1992 (Progr. in Math. Birkh\u00e4user).","DOI":"10.1007\/978-1-4612-2752-6_7"},{"key":"13_CR9","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","volume":"24","author":"J. Heintz","year":"1983","unstructured":"Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theor. Comp. Sci. 24, 1983, pp. 239\u2013278.","journal-title":"Theor. Comp. Sci."},{"key":"13_CR10","volume-title":"Technical Report TR-89-027","author":"M. Karpinski","year":"1989","unstructured":"Karpinski, M., Boolean Circuit Complexity of Algebraic Interpolation Problems, Technical Report TR-89-027, International Computer Science Institute, Berkeley, 1989; in Proc. CSL'88, Lecture Notes in Computer Science 385, 1989, pp. 138\u2013147."},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Khovanski, A., Fewnomials, Transl. Math. Monogr., AMS 88, 1991.","DOI":"10.1090\/mmono\/088"},{"key":"13_CR12","unstructured":"Kaltofen, E. & Yagati, L., Improved sparse multivariate interpolation, Report 88-17, Dept. Comput. Sci., Rensselaer Polytechnic Institute, 1988."}],"container-title":["Lecture Notes in Computer Science","Applied Algebra, Algebraic Algorithms and Error-Correcting Codes"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56686-4_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T04:54:13Z","timestamp":1640926453000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56686-4_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540566861","9783540476306"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-56686-4_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}