{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T08:44:59Z","timestamp":1758703499291},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,12,8]],"date-time":"2017-12-08T00:00:00Z","timestamp":1512691200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Syst Sci Complex"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s11424-017-6332-0","type":"journal-article","created":{"date-parts":[[2017,12,8]],"date-time":"2017-12-08T04:06:23Z","timestamp":1512705983000},"page":"552-568","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computing Sparse GCD of Multivariate Polynomials via Polynomial Interpolation"],"prefix":"10.1007","volume":"31","author":[{"given":"Min","family":"Tang","sequence":"first","affiliation":[]},{"given":"Bingyu","family":"Li","sequence":"additional","affiliation":[]},{"given":"Zhenbing","family":"Zeng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,8]]},"reference":[{"issue":"4","key":"6332_CR1","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1145\/321662.321664","volume":"18","author":"W S Brown","year":"1971","unstructured":"Brown W S, On Euclid\u2019s algorithm and the computation of polynomial greatest common divisors, Journal of the ACM, 1971, 18(4): 478\u2013504.","journal-title":"Journal of the ACM"},{"issue":"4","key":"6332_CR2","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1145\/321662.321665","volume":"18","author":"W S Brown","year":"1971","unstructured":"Brown W S and Traub J F, On Euclid\u2019s algorithm and the theory of subresultants, Journal of the ACM, 1971, 18(4): 505\u2013514.","journal-title":"Journal of the ACM"},{"issue":"1","key":"6332_CR3","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1145\/321371.321381","volume":"14","author":"G E Collins","year":"1967","unstructured":"Collins G E, Subresultants and reduced polynomial remainder sequences, Journal of the ACM, 1967, 14(1): 128\u2013142.","journal-title":"Journal of the ACM"},{"key":"6332_CR4","first-page":"297","volume-title":"Proceedings of Symbolic and Algebraic Computation, International Symposium ISSAC","author":"M V Hoeij","year":"2004","unstructured":"Hoeij M V and Monagan M, Algorithms for polynomial GCD computation over algebraic function fields, Proceedings of Symbolic and Algebraic Computation, International Symposium ISSAC 2004, Santander, 2004, 297\u2013304."},{"key":"6332_CR5","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1145\/1277548.1277575","volume-title":"Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation","author":"S M M Javadi","year":"2007","unstructured":"Javadi S M M and Monagan M, A sparse modular gcd algorithm for polynomials over algebraic function fields, Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, Canada, 2007, 187\u2013194."},{"key":"6332_CR6","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1016\/j.sigpro.2009.09.024","volume":"90","author":"W Z Qiu","year":"2010","unstructured":"Qiu W Z and Skafidas E, Robust estimation of GCD with sparse coefficients, Signal Processing, 2010, 90: 972\u2013976.","journal-title":"Signal Processing"},{"key":"6332_CR7","volume-title":"Proceedings of the International Congress of Mathematicians","author":"E J Cand\u00e8s","year":"2014","unstructured":"Cand\u00e8s E J, Mathematics of sparsity (and a few other things), Proceedings of the International Congress of Mathematicians, Seoul, 2014."},{"key":"6332_CR8","first-page":"285","volume-title":"Proceedings of International Symposium on Symbolic and Algebraic Computation Cambridge","author":"B W Char","year":"1984","unstructured":"Char B W and Geddes K O and Gonnet G H, GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation, Proceedings of International Symposium on Symbolic and Algebraic Computation Cambridge, England, 1984, 285\u2013296."},{"key":"6332_CR9","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1145\/800192.805698","volume-title":"Proceedings of ACM Annual Conference","author":"J Moses","year":"1973","unstructured":"Moses J and Yun D Y Y, The EZGCD algorithm, Proceedings of ACM Annual Conference, Munich, 1973, 159\u2013166."},{"issue":"2","key":"6332_CR10","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1145\/321879.321890","volume":"22","author":"D R Musser","year":"2009","unstructured":"Musser D R, Multivariate polynomial factoring, Journal of the ACM, 2009, 22(2): 291\u2013308.","journal-title":"Journal of the ACM"},{"issue":"131","key":"6332_CR11","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1090\/S0025-5718-1975-0396471-3","volume":"29","author":"P S Wang","year":"1975","unstructured":"Wang P S and Rothschild L P, Factoring multivariate polynomials over the integers, Mathematics of Computation, 1975, 29(131): 935\u2013950.","journal-title":"Mathematics of Computation"},{"issue":"3","key":"6332_CR12","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0022-314X(69)90047-X","volume":"1","author":"H Zassenhaus","year":"1969","unstructured":"Zassenhaus H, On Hensel factorization I, Journal of Number Theory, 1969, 1(3): 291\u2013311.","journal-title":"Journal of Number Theory"},{"key":"6332_CR13","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1145\/1277548.1277575","volume-title":"Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation","author":"S M M Javadi","year":"2007","unstructured":"Javadi S M M and Monagan M, A sparse modular gcd algorithm for polynomials over algebraic function fields, Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, Canada, 2007, 187\u2013194."},{"key":"6332_CR14","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume":"72","author":"R Zippel","year":"1979","unstructured":"Zippel R, Probabilistic algorithms for sparse polynomials, Lecture Notes in Computer Science, 1979, 72: 216\u2013226.","journal-title":"Lecture Notes in Computer Science"},{"key":"6332_CR15","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/1073884.1073903","volume-title":"Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation","author":"J Kleine De","year":"2005","unstructured":"De Kleine J, Monagan M, and Wittkopf A, Algorithms for the non-monic case of the sparse modular GCD algorithm, Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, Beijing, 2005, 124\u2013131."},{"key":"6332_CR16","first-page":"301","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing","author":"M Ben-Or","year":"1988","unstructured":"Ben-Or M and Tiwari P, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, New York, 1988, 301\u2013309."},{"key":"6332_CR17","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/1993886.1993900","volume-title":"Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation","author":"C Bright","year":"2011","unstructured":"Bright C and Storjohann A, Vector rational number reconstruction, Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, San Jose, California, 2011, 51\u201358."},{"key":"6332_CR18","first-page":"539","volume-title":"Theoretical Informatics","author":"M V Hoeij","year":"2010","unstructured":"Hoeij M V and Novocin A, Gradual sub-lattice reduction and a new complexity for factoring polynomials, Theoretical Informatics, 6034 of Lecture Notes in Computer Science, 2010, 539\u2013553."},{"issue":"2","key":"6332_CR19","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/1089220.1089228","volume":"14","author":"P S Wang","year":"1980","unstructured":"Wang P S, The EEZ-GCD algorithm, SIGSAM Bull, 1980, 14(2): 50\u201360.","journal-title":"SIGSAM Bull"},{"issue":"16","key":"6332_CR20","doi-asserted-by":"publisher","first-page":"1445","DOI":"10.1016\/j.tcs.2010.11.050","volume":"412","author":"A Cuyt","year":"2011","unstructured":"Cuyt A and Lee W S, Sparse interpolation of multivariate rational functions, Theoretical Computer Science, 2011, 412(16): 1445\u20131456.","journal-title":"Theoretical Computer Science"},{"key":"6332_CR21","doi-asserted-by":"crossref","unstructured":"Grigoriev D Y and Karpinski M, The matching problem for bipartite graphs with polynomially bounded permanents is in NC, University of Bonn, 857-CS, 1986.","DOI":"10.1109\/SFCS.1987.56"}],"container-title":["Journal of Systems Science and Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11424-017-6332-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11424-017-6332-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11424-017-6332-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T01:52:56Z","timestamp":1660096376000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11424-017-6332-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,8]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["6332"],"URL":"https:\/\/doi.org\/10.1007\/s11424-017-6332-0","relation":{},"ISSN":["1009-6124","1559-7067"],"issn-type":[{"value":"1009-6124","type":"print"},{"value":"1559-7067","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,8]]}}}