{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:17Z","timestamp":1750220357701,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:00:00Z","timestamp":1598918400000},"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":["ACM Commun. Comput. Algebra"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p>\n            The applications of solving systems of polynomial equations are legion: The real case permeates all of non-linear optimization as well as numerous problems in engineering. The\n            <jats:italic>p<\/jats:italic>\n            -adic case leads to many classical questions in number theory, and is close to many applications in cryptography, coding theory, and computational number theory. As such, it is important to understand the complexity of solving systems of polynomial equations over local fields. Furthermore, the complexity of solving\n            <jats:italic>structured<\/jats:italic>\n            systems --- such as those with a fixed number of monomial terms or invariance with respect to a group action --- arises naturally in many computational geometric applications and is closely related to a deeper understanding of circuit complexity (see, e.g., [8]). Clearly, if we are to fully understand the complexity of solving sparse polynomial systems, then we should at least be able to settle the univariate case, e.g., classify when it is possible to separate and approximate roots in deterministic time polynomial in the input size.\n          <\/jats:p>","DOI":"10.1145\/3457341.3457343","type":"journal-article","created":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T22:07:02Z","timestamp":1615846022000},"page":"86-90","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A complexity chasm for solving sparse polynomial equations over\n            <i>p<\/i>\n            -adic fields"],"prefix":"10.1145","volume":"54","author":[{"given":"J. Maurice","family":"Rojas","sequence":"first","affiliation":[{"name":"Texas A&amp;M University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuyu","family":"Zhu","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.11.008"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/236590"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157013000089"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-013-0200-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/648185.749909"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2012.03.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2019.02.004"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2014.09.036"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3431"},{"key":"e_1_2_1_10_1","first-page":"277","article-title":"On the factorization of lacunary polynomials","volume":"1","author":"Lenstra Hendrik W","year":"1999","unstructured":"Hendrik W Lenstra . On the factorization of lacunary polynomials . Number Theory in Progress , 1 : 277 -- 291 , 1999 . Hendrik W Lenstra. On the factorization of lacunary polynomials. Number Theory in Progress, 1:277--291, 1999.","journal-title":"Number Theory in Progress"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028999140"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01198012"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02546329"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4310\/MRL.1998.v5.n3.a2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3254-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.09.007"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608632"},{"key":"e_1_2_1_18_1","series-title":"Cambridge Studies in Advanced Mathematics","volume-title":"Ultrametric calculus","author":"Schikhof W. H.","year":"2006","unstructured":"W. H. Schikhof . Ultrametric calculus , volume 4 of Cambridge Studies in Advanced Mathematics . Cambridge University Press , Cambridge , 2006 . An introduction to p-adic analysis, Reprint of the 1984 original [MR0791759]. W. H. Schikhof. Ultrametric calculus, volume 4 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2006. An introduction to p-adic analysis, Reprint of the 1984 original [MR0791759]."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9884-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1998.0228"},{"key":"e_1_2_1_21_1","series-title":"International series in pure and applied mathematics","volume-title":"Algebraic number theory","author":"Weiss Edwin","year":"1963","unstructured":"Edwin Weiss . Algebraic number theory . International series in pure and applied mathematics . McGraw-Hill , 1963 . Edwin Weiss. Algebraic number theory. International series in pure and applied mathematics. McGraw-Hill, 1963."},{"key":"e_1_2_1_22_1","first-page":"9","volume-title":"Some Estimated Likelihoods for Computational Complexity","author":"Williams R. Ryan","year":"2019","unstructured":"R. Ryan Williams . Some Estimated Likelihoods for Computational Complexity , pages 9 -- 26 . Springer International Publishing , Cham , 2019 . R. Ryan Williams. Some Estimated Likelihoods for Computational Complexity, pages 9--26. Springer International Publishing, Cham, 2019."},{"key":"e_1_2_1_23_1","volume-title":"Linear forms in p-adic logarithms III. Compositio Mathematica, 3(241--276)","author":"Yu Kunrui","year":"1994","unstructured":"Kunrui Yu . Linear forms in p-adic logarithms III. Compositio Mathematica, 3(241--276) , 1994 . Kunrui Yu. Linear forms in p-adic logarithms III. Compositio Mathematica, 3(241--276), 1994."}],"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457341.3457343","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457341.3457343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:19Z","timestamp":1750191439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457341.3457343"}},"subtitle":["extended abstract"],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1145\/3457341.3457343"],"URL":"https:\/\/doi.org\/10.1145\/3457341.3457343","relation":{},"ISSN":["1932-2240"],"issn-type":[{"type":"print","value":"1932-2240"}],"subject":[],"published":{"date-parts":[[2020,9]]},"assertion":[{"value":"2021-03-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}