{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:20:05Z","timestamp":1758709205153},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1991,3,1]],"date-time":"1991-03-01T00:00:00Z","timestamp":667785600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1991,3]]},"DOI":"10.1007\/bf01200058","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T13:41:22Z","timestamp":1109252482000},"page":"67-90","source":"Crossref","is-referenced-by-count":8,"title":["On the decidability of sparse univariate polynomial interpolation"],"prefix":"10.1007","volume":"1","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prasoon","family":"Tiwari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"M. Ben-Or and P. Tiwari, A deterministic algorithm for sparse multivariate polynomial interpolation,Proc. 20th Ann. ACM Symp. Theory of Computing, 301?309, 1988.","DOI":"10.1145\/62212.62241"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"L. Blum, M. Shub and S. Smale, On a theory of computation over the real number; NP completeness, recursive functions and universal machines,Proc. 29th IEEE Symp. Foundations of Comp. Sci., 387?397, 1988.","DOI":"10.1109\/SFCS.1988.21955"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"A. Borodin and P. Tiwari, On the decidability of sparse univariate polynomial interpolation (preliminary version),Proc. 22nd Ann. ACM Symp. Theory of Computing, 535?545, 1990.","DOI":"10.1145\/100216.100292"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1090\/S0002-9939-1976-0412205-0","volume":"58","author":"R. J. Evans","year":"1976","unstructured":"R. J. Evans andI. M. Isaacs, Generalized Vandermonde determinants and roots of unity of prime order,Proc. Amer. Math. Soc. 58 (1976), 51?54.","journal-title":"Proc. Amer. Math. Soc."},{"key":"CR5","volume-title":"The Theory of Matrices","author":"F. R. Gantmacher","year":"1959","unstructured":"F. R. Gantmacher,The Theory of Matrices, K. A. Hirsch, New York, 1959."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"D. Yu. Grigoriev and M. Karpinski, The matching problem for bipartite graphs with polynomially bounded permanents is in NC,Proc. 28th IEEE Symp. Foundations of Comp. Sci., 166?172, 1987.","DOI":"10.1109\/SFCS.1987.56"},{"key":"CR7","volume-title":"Basic Algebra I","author":"N. Jacobson","year":"1974","unstructured":"N. Jacobson,Basic Algebra I, W. H. Freeman and Company, San Francisco, 1974."},{"key":"CR8","series-title":"Technical Report TR-89060","volume-title":"Learnability and VC-dimension of sparse polynomials and rational functions","author":"M. Karpinski","year":"1989","unstructured":"M. Karpinski andT. Werther,Learnability and VC-dimension of sparse polynomials and rational functions, Technical Report TR-89060, International Computer Science Institute, Berkeley, 1989."},{"key":"CR9","unstructured":"D. E. Littlewood,The Theory of Group Characters and Matrix Representations of Groups, Oxford, 1950."},{"key":"CR10","volume-title":"Basic Algebra, A Survey of Matrix Theory and Matrix Inequalities","author":"M. Marcus","year":"1964","unstructured":"M. Marcus andH. Minc,Basic Algebra, A Survey of Matrix Theory and Matrix Inequalities, Allyn and Bacon, Boston, Mass., 1964."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities,J. Assoc. Comput. Mach. 27 (1980), 701?707.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR12","series-title":"IBM Research Report 12766","volume-title":"Parallel algorithms for instances of linear matroid parity with a small number of solutions","author":"P. Tiwari","year":"1987","unstructured":"P. Tiwari,Parallel algorithms for instances of linear matroid parity with a small number of solutions, IBM Research Report 12766, IBM T. J. Watson Research Center, New York, 1987."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"R. Zippel, Probabilistic algorithms for sparse polynomials.Lecture Notes in Computer Science 72,Symbolic and Algebraic Computation, 216?226, Springer-Verlag, 1979.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200058.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200058\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T22:38:07Z","timestamp":1586126287000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,3]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,3]]}},"alternative-id":["BF01200058"],"URL":"https:\/\/doi.org\/10.1007\/bf01200058","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,3]]}}}