{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T02:02:50Z","timestamp":1760061770034},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667230"},{"type":"electronic","value":"9783540467960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46796-3_47","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T11:14:33Z","timestamp":1186053273000},"page":"492-497","source":"Crossref","is-referenced-by-count":4,"title":["On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]},{"given":"Igor","family":"Shparlinski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"key":"47_CR1","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1112\/plms\/s3-43.2.227","volume":"43","author":"S. D. Cohen","year":"1981","unstructured":"S. D. Cohen, \u2018The distribution of Galois groups and Hilbert\u2019s irreducibility theorem\u2019;, Proc. London Math. Soc., 43 (1981), 227\u2013250.","journal-title":"Proc. London Math. Soc"},{"key":"47_CR2","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0019-3577(98)80001-3","volume":"9","author":"P. Corvaja","year":"1998","unstructured":"P. Corvaja and U. Zannier, \u2018Diophantine equations with power sums and universal Hilbert sets\u2019, Indag. Math., 9 (1998), 317\u2013332.","journal-title":"Indag. Math"},{"key":"47_CR3","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1006\/jsco.1998.0242","volume":"27","author":"F. Cucker","year":"1999","unstructured":"F. Cucker, P. Koiran and S. Smale, \u2018A polynomial time algorithm for Diophantine equations in one variable\u2019, J. Symb. Comp., 27 (1999), 21\u201329.","journal-title":"J. Symb. Comp"},{"key":"47_CR4","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02567509","volume":"89","author":"P. D\u00e9bes","year":"1996","unstructured":"P. D\u00e9bes, \u2018Hilbert subsets and S-integral points\u2019, Manuscr. Math., 89 (1996), 107\u2013137.","journal-title":"Manuscr. Math"},{"key":"47_CR5","unstructured":"P. \u00e9Dbes, \u2018Density results on Hilbert subsets\u2019, Preprint, 1996, 1\u201325."},{"key":"47_CR6","doi-asserted-by":"crossref","unstructured":"A. Diaz and E. Kaltofen, \u2018On computing greatest common divisors with polynomials given by black boxes for their evaluations\u2019, Proc. Intern. Symp. on Symb. and Algebraic Comp., 1995, 232\u2013239.","DOI":"10.1145\/220346.220375"},{"key":"47_CR7","volume-title":"Computers and Intractability","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability, W. H. Feeman, NY, 1979."},{"key":"47_CR8","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0022-0000(85)90043-1","volume":"31","author":"J. Gathen von zur","year":"1985","unstructured":"J. von zur Gathen, \u2018Irreducibility of multivariate polynomials\u2019, J. Comp. and Syst. Sci., 31 (1985), 225\u2013264.","journal-title":"J. Comp. and Syst. Sci"},{"key":"47_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(85)90044-3","volume":"31","author":"J. Gathen von zur","year":"1985","unstructured":"J. von zur Gathen and E. Kaltofen, \u2018Factoring sparse multivariate polynomials\u2019, J. Comp. and Syst. Sci., 31 (1985), 265\u2013287.","journal-title":"J. Comp. and Syst. Sci"},{"key":"47_CR10","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/BF01202042","volume":"6","author":"J. Gathen von zur","year":"1997","unstructured":"J. von zur Gathen, M. Karpinski and I. E. Shparlinski, \u2018Counting points on curves over finite fields\u2019, Comp. Compl., 6 (1997), 64\u201399.","journal-title":"Comp. Compl"},{"key":"47_CR11","doi-asserted-by":"crossref","first-page":"297","DOI":"10.3233\/FI-1996-283406","volume":"28","author":"D. Grigoriev","year":"1996","unstructured":"D. Grigoriev, M. Karpinski and A. M. Odlyzko, \u2018Short proof of nondivisibility of sparse polynomials under the Extended Riemann Hypothesis\u2019, Fundamenta Informaticae, 28 (1996), 297\u2013301.","journal-title":"Fundamenta Informaticae"},{"key":"47_CR12","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1137\/0219073","volume":"19","author":"D. Grigoriev","year":"1990","unstructured":"D. Grigoriev, M. Karpinski and M. Singer, \u2018Fast parallel algorithm for sparse multivariate polynomials over finite fields\u2019, SIAM J. Comput., 19 (1990), 1059\u20131063.","journal-title":"SIAM J. Comput"},{"key":"47_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539791194069","volume":"23","author":"D. Grigoriev","year":"1994","unstructured":"D. Grigoriev, M. Karpinski and M. Singer, \u2018Computational complexity of sparse rational interpolation\u2019, SIAM J. Comput., 23 (1994), 1\u201311.","journal-title":"SIAM J. Comput"},{"key":"47_CR14","first-page":"50","volume-title":"Extended Hilbert irreducibility and its applications","author":"M.-D.A. Huang","year":"1998","unstructured":"M.-D.A. Huang and Y.-C. Wong, \u2018Extended Hilbert irreducibility and its applications\u2019, Proc. 9-th Annual ACM-SIAM Symp. on Discr. Algorithms, ACM, NY, 1998, 50\u201358."},{"key":"47_CR15","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0747-7171(08)80015-6","volume":"9","author":"E. Kaltofen","year":"1990","unstructured":"E. Kaltofen and B. M. Trager, \u2018Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separations of nominators and denominators\u2019, J. Symb. Comp., 9 (1990), 301\u2013320.","journal-title":"J. Symb. Comp"},{"key":"47_CR16","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0304-3975(95)00162-X","volume":"157","author":"M. Karpinski","year":"1996","unstructured":"M. Karpinski and I. E. Shparlinski, \u2018On some approximation problems concerning sparse polynomials over finite fields\u2019, Theor. Comp.. Sci., 157 (1996), 259\u2013266.","journal-title":"Theor. Comp.. Sci"},{"key":"47_CR17","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/S0022-0000(77)80013-5","volume":"14","author":"D. A. Plaisted","year":"1977","unstructured":"D. A. Plaisted, \u2018Sparse complex polynomials and polynomial reducibility\u2019, J. Comp. Sys. Sci., 14 (1977), 210\u2013221.","journal-title":"J. Comp. Sys. Sci"},{"key":"47_CR18","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1137\/0207036","volume":"7","author":"D. A. Plaisted","year":"1978","unstructured":"D. A. Plaisted, \u2018Some polynomial and integer divisibility problems are NP-hard\u2019, SIAM J. Comput., 7 (1978), 458\u2013464.","journal-title":"SIAM J. Comput"},{"key":"47_CR19","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0304-3975(84)90130-0","volume":"31","author":"D. A. Plaisted","year":"1984","unstructured":"D. A. Plaisted, \u2018New NP-hard and NP-complete polynomial and integer divisibility problems\u2019, Theor. Comp.. Sci., 31 (1984), 125\u2013138.","journal-title":"Theor. Comp.. Sci"},{"key":"47_CR20","doi-asserted-by":"crossref","first-page":"293","DOI":"10.4064\/aa-69-3-293-302","volume":"69","author":"A. Schinzel","year":"1995","unstructured":"A. Schinzel and U. Zannier, \u2018The least admissible value of the parameter in Hilbert\u2019s Irreducibility Theorem\u2019, Acta Arithm., 69 (1995), 293\u2013302.","journal-title":"Acta Arithm"},{"key":"47_CR21","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1006\/jsco.1994.1025","volume":"17","author":"V. Shoup","year":"1994","unstructured":"V. Shoup, \u2018Fast construction of irreducible polynomials over finite fields\u2019, J. Symb. Comp., 17 (1994), 371\u2013391.","journal-title":"J. Symb. Comp"},{"key":"47_CR22","first-page":"703","volume":"322","author":"U. Zannier","year":"1996","unstructured":"U. Zannier, \u2018Note on dense universal Hilbert sets\u2019, C.R. Acad. Sci. Paris, Ser.I, 322 (1996), 703\u2013706.","journal-title":"C.R. Acad. Sci. Paris"}],"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-46796-3_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T14:52:16Z","timestamp":1587826336000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46796-3_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667230","9783540467960"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-46796-3_47","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}