{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T15:12:34Z","timestamp":1761059554868,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,26]],"date-time":"2013-06-26T00:00:00Z","timestamp":1372204800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,6,26]]},"DOI":"10.1145\/2465506.2465514","type":"proceedings-article","created":{"date-parts":[[2013,6,25]],"date-time":"2013-06-25T19:13:21Z","timestamp":1372187601000},"page":"61-68","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Sub-linear root detection, and new hardness results, for sparse polynomials over finite fields"],"prefix":"10.1145","author":[{"given":"Jingguo","family":"Bi","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qi","family":"Cheng","sequence":"additional","affiliation":[{"name":"University of Oklahoma, Norman, OK, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Maurice","family":"Rojas","sequence":"additional","affiliation":[{"name":"Texas A & M University, College Station, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6,26]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1016\/j.jsc.2011.09.007"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1016\/j.jco.2006.06.002"},{"key":"e_1_3_2_1_3_1","volume-title":"Efficient Algorithms","author":"Bach Eric","year":"1996","unstructured":"Bach , Eric and Shallit , Jeff , Algorithmic Number Theory , Vol. I : Efficient Algorithms , MIT Press , Cambridge, MA , 1996 . Bach, Eric and Shallit, Jeff, Algorithmic Number Theory, Vol. I: Efficient Algorithms, MIT Press, Cambridge, MA, 1996."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1090\/conm\/556\/11012"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry, Algorithms and Computationin Mathematics","author":"Basu Pollack","year":"2006","unstructured":"Basu , Saugata; Pollack , Ricky; and Roy , Marie-Francoise , Algorithms in Real Algebraic Geometry, Algorithms and Computationin Mathematics , vol. 10 , Springer-Verlag , 2006 . Basu, Saugata; Pollack, Ricky; and Roy, Marie-Francoise, Algorithms in Real Algebraic Geometry, Algorithms and Computationin Mathematics, vol. 10, Springer-Verlag, 2006."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1145\/1576702.1576711"},{"key":"e_1_3_2_1_8_1","volume-title":"Algebraic complexity theory, with the collaboration of Thomas Lickteig, Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences}, 315","author":"B\u00fcrgisser Clausen","year":"1997","unstructured":"B\u00fcrgisser , Peter; Clausen , Michael; and Shokrollahi , M . Amin , Algebraic complexity theory, with the collaboration of Thomas Lickteig, Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences}, 315 , Springer-Verlag , Berlin , 1997 . B\u00fcrgisser, Peter; Clausen, Michael; and Shokrollahi, M. Amin, Algebraic complexity theory, with the collaboration of Thomas Lickteig, Grundlehren der Mathematischen Wissenschaften {Fundamental Principles of Mathematical Sciences}, 315, Springer-Verlag, Berlin, 1997."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1007\/s11856-000-1270-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1090\/S0025-5718-1981-0606517-5"},{"unstructured":"Cheng Qi; Hill Joshua E.; and Wan Daqing \"Counting Value Sets: Algorithm and Complexity \" Math ArXiV preprint 1111.1224 . Cheng Qi; Hill Joshua E.; and Wan Daqing \"Counting Value Sets: Algorithm and Complexity \" Math ArXiV preprint 1111.1224 .","key":"e_1_3_2_1_11_1"},{"doi-asserted-by":"crossref","unstructured":"Christopher John \"The Asymptotic Density of Some k-Dimensional Sets \" the American Mathematical Monthly vol. 63 no. 6 (Jun.--Jul. 1956) pp. 399--401. Christopher John \"The Asymptotic Density of Some k-Dimensional Sets \" the American Mathematical Monthly vol. 63 no. 6 (Jun.--Jul. 1956) pp. 399--401.","key":"e_1_3_2_1_12_1","DOI":"10.2307\/2309400"},{"key":"e_1_3_2_1_13_1","volume-title":"August","author":"Cox David A","year":"2004","unstructured":"Cox , David A . , personal communication , August , 2004 . Cox, David A., personal communication, August, 2004."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1006\/jsco.1998.0242"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1016\/j.jco.2004.03.003"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1145\/1145768.1145770"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1007\/BF01202042"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1006\/jsco.1999.1002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1007\/BF01272074"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-8176-4771-1","volume-title":"Resultants and Multidimensional Determinants","author":"Gel'fand Israel","year":"1994","unstructured":"Gel'fand , Israel Moseyevitch; Kapranov , Misha M.; and Zelevinsky , Andrei V Discriminants , Resultants and Multidimensional Determinants , Birkh\u00e4user , Boston , 1994 . Gel'fand, Israel Moseyevitch; Kapranov, Misha M.; and Zelevinsky, Andrei V Discriminants, Resultants and Multidimensional Determinants, Birkh\u00e4user, Boston, 1994."},{"key":"e_1_3_2_1_21_1","first-page":"216","volume-title":"Sympos. Math. XXXIV","author":"Giusti Marc","unstructured":"Giusti , Marc and Heintz , Joos , \" La d\u00e9termination des points isol\u00e9s et la dimension d'une vari\u00e9t\u00e9 alg\u00e9brique peut se faire en temps polynomial,\" Computational Algebraic Geometry and Commutative Algebra (Cortona,1991) , Sympos. Math. XXXIV , pp. 216 -- 256 , Cambridge University Giusti, Marc and Heintz, Joos, \"La d\u00e9termination des points isol\u00e9s et la dimension d'une vari\u00e9t\u00e9 alg\u00e9brique peut se faire en temps polynomial,\" Computational Algebraic Geometry and Commutative Algebra (Cortona,1991), Sympos. Math. XXXIV, pp. 216--256, Cambridge University"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1016\/S0022-0000(02)00024-7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1006\/jcss.2000.1727"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1016\/j.jsc.2006.03.006"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1145\/860854.860857"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1145\/1073884.1073914"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1090\/S0025-5718-98-00944-2"},{"key":"e_1_3_2_1_28_1","first-page":"492","volume-title":"HI","author":"Karpinski Marek","year":"1999","unstructured":"Karpinski , Marek and Shparlinski , Igor E \"On the computational hardness of testing square-freeness ofsparse polynomials,\" Applied algebra , algebraic algorithms anderror-correcting codes (Honolulu , HI , 1999 ), pp. 492 -- 497 ,Lecture Notes in Comput. Sci., 1719, Springer , Berlin, 1999. Karpinski, Marek and Shparlinski, Igor E \"On the computational hardness of testing square-freeness ofsparse polynomials,\" Applied algebra, algebraic algorithms anderror-correcting codes (Honolulu, HI, 1999), pp. 492--497,Lecture Notes in Comput. Sci., 1719, Springer, Berlin, 1999."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1137\/08073408X"},{"doi-asserted-by":"crossref","unstructured":"Kipnis Aviad and Shamir Adi \"Cryptanalysis of the HFE public key cryptosystem by relinearization \"Advances in cryptology -- CRYPTO '99 ( Santa Barbara CA) pp. 19 -- 30 Lecture Notes in Comput . Sci. 1666 Springer Berlin 1999 . Kipnis Aviad and Shamir Adi \"Cryptanalysis of the HFE public key cryptosystem by relinearization \"Advances in cryptology -- CRYPTO '99 (Santa Barbara CA) pp. 19--30 Lecture Notes in Comput. Sci. 1666 Springer Berlin 1999.","key":"e_1_3_2_1_30_1","DOI":"10.1007\/3-540-48405-1_2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1007\/BF01457454"},{"key":"e_1_3_2_1_32_1","volume-title":"Berlin","author":"Jr Hendrik W","year":"1997","unstructured":"Lenstra ( Jr .), Hendrik W . , \" Finding Small Degree Factors of Lacunary Polynomials ,\" Number Theory in Progress , Vol . 1 ( Zakopane-K\u00f3scielisko , 1997 ), pp. 267--276, de Gruyter , Berlin , 1999. Lenstra (Jr.), Hendrik W., \"Finding Small Degree Factors of Lacunary Polynomials,\" Number Theory inProgress, Vol. 1 (Zakopane-K\u00f3scielisko, 1997), pp. 267--276, de Gruyter, Berlin, 1999."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1016\/j.ejc.2004.07.009"},{"key":"e_1_3_2_1_34_1","article-title":"A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations","author":"Micciancio D.","unstructured":"Micciancio , D. and Voulgaris , P ., \" A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations ,\" SIAM J. Computing, special issue, to appear. Micciancio, D. and Voulgaris, P., \"A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations,\" SIAM J. Computing, special issue, to appear.","journal-title":"SIAM J. Computing, special issue, to appear."},{"key":"e_1_3_2_1_35_1","first-page":"6632","article-title":"Lattice Reduction Algorithms: Theory and Practice","volume":"2011","author":"Nguyen Phong Q","year":"2011","unstructured":"Nguyen , Phong Q . , \" Lattice Reduction Algorithms: Theory and Practice ,\" K. G. Paterson (ed.): Eurocrypt 2011 , LNCS 6632 , pp. 2--6, 2011 . Nguyen, Phong Q., \"Lattice Reduction Algorithms: Theory and Practice,\" K. G. Paterson (ed.): Eurocrypt 2011, LNCS 6632, pp. 2--6, 2011.","journal-title":"K. G. Paterson (ed.): Eurocrypt"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1016\/0304-3975(84)90130-0"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198534938.001.0001","volume-title":"Analytic Theory of Polynomials","author":"Rahman Qazi","year":"2002","unstructured":"Rahman , Qazi Ibadur; and Schmeisser , Gerhard , Analytic Theory of Polynomials , Clarendon Press ,London Mathematical Society Monographs 26, 2002 . Rahman, Qazi Ibadur; and Schmeisser, Gerhard, Analytic Theory of Polynomials, Clarendon Press,London Mathematical Society Monographs 26, 2002."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1016\/j.jco.2004.03.004"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1145\/322217.322225"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1016\/0304-3975(95)00164-6"},{"key":"e_1_3_2_1_41_1","volume-title":"Marcia L., The Geometry of Ren\u00e9 Descartes, translated from the French and Latin (with a facsimile of Descartes' 1637 French edition)","author":"Smith","year":"1954","unstructured":"Smith , David Eugene and Latham , Marcia L., The Geometry of Ren\u00e9 Descartes, translated from the French and Latin (with a facsimile of Descartes' 1637 French edition) , Dover Publications Inc ., New York ( 1954 ). Smith, David Eugene and Latham, Marcia L., The Geometry of Ren\u00e9 Descartes, translated from the French and Latin (with a facsimile of Descartes' 1637 French edition), Dover Publications Inc., New York (1954)."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.4310\/MRL.2005.v12.n1.a11"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_43_1","DOI":"10.1145\/1374376.1374445"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_44_1","DOI":"10.1145\/1806689.1806723"},{"key":"e_1_3_2_1_45_1","volume-title":"Department of Computer Science","author":"Zippel Richard","year":"1989","unstructured":"Zippel , Richard , \"An explicit separation of relativised random polynomial time and relativised deterministic polynomial time,\" Technical report #965 , Department of Computer Science , Cornell University , 1989 . Zippel, Richard, \"An explicit separation of relativised random polynomial time and relativised deterministic polynomial time,\" Technical report #965, Department of Computer Science, Cornell University, 1989."}],"event":{"sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"acronym":"ISSAC'13","name":"ISSAC'13: International Symposium on Symbolic and Algebraic Computation","location":"Boston Maine USA"},"container-title":["Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2465506.2465514","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2465506.2465514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:35Z","timestamp":1750234715000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2465506.2465514"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,26]]},"references-count":45,"alternative-id":["10.1145\/2465506.2465514","10.1145\/2465506"],"URL":"https:\/\/doi.org\/10.1145\/2465506.2465514","relation":{},"subject":[],"published":{"date-parts":[[2013,6,26]]},"assertion":[{"value":"2013-06-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}