{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:45:36Z","timestamp":1770281136478,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T00:00:00Z","timestamp":1659398400000},"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":[[2022,8,2]]},"DOI":"10.1145\/3531130.3533331","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T20:23:38Z","timestamp":1659644618000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Identity Testing for Radical Expressions"],"prefix":"10.1145","author":[{"given":"Nikhil","family":"Balaji","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Delhi, India"}]},{"given":"Klara","family":"Nosan","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9, CNRS, IRIF, F-75013, Paris, France, France"}]},{"given":"Mahsa","family":"Shirmohammadi","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9, CNRS, IRIF, F-75013, Paris, France, France"}]},{"given":"James","family":"Worrell","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792540"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"M. Agrawal N. Kayal and N. Saxena. 2004. PRIMES is in P. Annals of mathematics(2004) 781\u2013793. M. Agrawal N. Kayal and N. Saxena. 2004. PRIMES is in P. Annals of mathematics(2004) 781\u2013793.","DOI":"10.4007\/annals.2004.160.781"},{"key":"e_1_3_2_1_3_1","volume-title":"Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS","author":"Akshay S.","year":"2020","unstructured":"S. Akshay , N. Balaji , A. Murhekar , R. Varma , and N. Vyas . 2020 . Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. S. Akshay, N. Balaji, A. Murhekar, R. Varma, and N. Vyas. 2020. Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"E. Allender P. B\u00fcrgisser J. Kjeldgaard-Pedersen and P.\u00a0B. Miltersen. 2006. On the complexity of numerical analysis. In CCC \u201906. 331\u2013339. E. Allender P. B\u00fcrgisser J. Kjeldgaard-Pedersen and P.\u00a0B. Miltersen. 2006. On the complexity of numerical analysis. In CCC \u201906. 331\u2013339.","DOI":"10.1109\/CCC.2006.30"},{"key":"e_1_3_2_1_5_1","volume-title":"14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings(Lecture Notes in Computer Science, Vol.\u00a02906)","author":"Arvind V.","year":"2003","unstructured":"V. Arvind and P.\u00a0 P. Kurur . 2003 . Upper Bounds on the Complexity of Some Galois Theory Problems. In Algorithms and Computation , 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings(Lecture Notes in Computer Science, Vol.\u00a02906) . Springer, 716\u2013725. V. Arvind and P.\u00a0P. Kurur. 2003. Upper Bounds on the Complexity of Some Galois Theory Problems. In Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings(Lecture Notes in Computer Science, Vol.\u00a02906). Springer, 716\u2013725."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1038"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"N. Balaji K. Nosan M. Shirmohammadi and J. Worrell. 2022. Identity testing for radical expressions. https:\/\/arxiv.org\/abs\/2202.07961 N. Balaji K. Nosan M. Shirmohammadi and J. Worrell. 2022. Identity testing for radical expressions. https:\/\/arxiv.org\/abs\/2202.07961","DOI":"10.1145\/3531130.3533331"},{"key":"e_1_3_2_1_8_1","volume-title":"International Symposium on Symbolic and Algebraic Computation","author":"Balaji N.","year":"2021","unstructured":"N. Balaji , S. Perifel , M. Shirmohammadi , and J. Worrell . 2021. Cyclotomic Identity Testing and Applications. In ISSAC \u201921 : International Symposium on Symbolic and Algebraic Computation , Virtual Event, Russia , July 18-23, 2021 . ACM, 35\u201342. N. Balaji, S. Perifel, M. Shirmohammadi, and J. Worrell. 2021. Cyclotomic Identity Testing and Applications. In ISSAC \u201921: International Symposium on Symbolic and Algebraic Computation, Virtual Event, Russia, July 18-23, 2021. ACM, 35\u201342."},{"key":"e_1_3_2_1_9_1","volume-title":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 32\u201346","author":"Benedikt M.","unstructured":"M. Benedikt , R. Lenhardt , and J. Worrell . 2013. LTL model checking of interval Markov chains . In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 32\u201346 . M. Benedikt, R. Lenhardt, and J. Worrell. 2013. LTL model checking of interval Markov chains. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 32\u201346."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1852"},{"key":"e_1_3_2_1_11_1","volume-title":"Nested Radicals. In 33rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 447\u2013456","author":"Bl\u00f6mer J.","year":"1992","unstructured":"J. Bl\u00f6mer . 1992 . How to Denest Ramanujan\u2019s Nested Radicals. In 33rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 447\u2013456 . J. Bl\u00f6mer. 1992. How to Denest Ramanujan\u2019s Nested Radicals. In 33rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 447\u2013456."},{"key":"e_1_3_2_1_12_1","volume-title":"5th Annual European Symposium, Proceedings(Lecture Notes in Computer Science, Vol.\u00a01284)","author":"Bl\u00f6mer J.","year":"1997","unstructured":"J. Bl\u00f6mer . 1997 . Denesting by Bounded Degree Radicals. In Algorithms - ESA \u201997 , 5th Annual European Symposium, Proceedings(Lecture Notes in Computer Science, Vol.\u00a01284) , R.\u00a0E. Burkard and G.\u00a0J. Woeginger (Eds.). Springer, 53\u201363. J. Bl\u00f6mer. 1997. Denesting by Bounded Degree Radicals. In Algorithms - ESA \u201997, 5th Annual European Symposium, Proceedings(Lecture Notes in Computer Science, Vol.\u00a01284), R.\u00a0E. Burkard and G.\u00a0J. Woeginger (Eds.). Springer, 53\u201363."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"J. Bl\u00f6mer. 1998. A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers. In Algorithms \u2014 ESA\u2019 98. 151\u2013162. J. Bl\u00f6mer. 1998. A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers. In Algorithms \u2014 ESA\u2019 98. 151\u2013162.","DOI":"10.1007\/3-540-68530-8_13"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"K. Chatterjee and R. Ibsen-Jensen. 2014. The complexity of ergodic mean-payoff games. In International Colloquium on Automata Languages and Programming. Springer 122\u2013133. K. Chatterjee and R. Ibsen-Jensen. 2014. The complexity of ergodic mean-payoff games. In International Colloquium on Automata Languages and Programming. Springer 122\u2013133.","DOI":"10.1007\/978-3-662-43951-7_11"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798341600"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2857050"},{"key":"e_1_3_2_1_18_1","volume-title":"A Course in Computational Algebraic Number Theory","author":"Cohen H.","unstructured":"H. Cohen . 2013. A Course in Computational Algebraic Number Theory . Springer Berlin Heidelberg . H. Cohen. 2013. A Course in Computational Algebraic Number Theory. Springer Berlin Heidelberg."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456725"},{"key":"e_1_3_2_1_20_1","unstructured":"E.\u00a0D. Demaine J.\u00a0S.\u00a0B. Mitchell and J. O\u2019Rourke. 2006. The open problems project: Problem 33. E.\u00a0D. Demaine J.\u00a0S.\u00a0B. Mitchell and J. O\u2019Rourke. 2006. The open problems project: Problem 33."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09680-3_20"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958052"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800113.803626"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"C. Haase and S. Kiefer. 2015. The odds of staying on budget. In International Colloquium on Automata Languages and Programming. Springer 234\u2013246. C. Haase and S. Kiefer. 2015. The odds of staying on budget. In International Colloquium on Automata Languages and Programming. Springer 234\u2013246.","DOI":"10.1007\/978-3-662-47666-6_19"},{"key":"e_1_3_2_1_26_1","volume-title":"Leibniz International Proceedings in Informatics, LIPIcs, Vol.\u00a083","author":"Haase C.","unstructured":"C. Haase , S. Kiefer , and M. Lohrey . 2017. Counting problems for Parikh images . In Leibniz International Proceedings in Informatics, LIPIcs, Vol.\u00a083 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 12. C. Haase, S. Kiefer, and M. Lohrey. 2017. Counting problems for Parikh images. In Leibniz International Proceedings in Informatics, LIPIcs, Vol.\u00a083. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 12."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","unstructured":"H. Iwaniec and E. Kowalski. 2004. Analytic number theory. Vol.\u00a053. AMS. H. Iwaniec and E. Kowalski. 2004. Analytic number theory. Vol.\u00a053. AMS.","DOI":"10.1090\/coll\/053"},{"key":"e_1_3_2_1_28_1","first-page":"375","article-title":"Factorization of Polynomials Given by Straight-Line","volume":"5","author":"Kaltofen E.","year":"1989","unstructured":"E. Kaltofen . 1989 . Factorization of Polynomials Given by Straight-Line Programs.Adv. Comput. Res. 5 (1989), 375 \u2013 412 . E. Kaltofen. 1989. Factorization of Polynomials Given by Straight-Line Programs.Adv. Comput. Res. 5(1989), 375\u2013412.","journal-title":"Programs.Adv. Comput. Res."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382559.2382560"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46678-0_19"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"S. Kiefer A. Murawski J. Ouaknine B. Wachter and J. Worrell. 2013. On the Complexity of Equivalence and Minimisation for Q-weighted Automata. Logical Methods in Computer Science 9 (2013). S. Kiefer A. Murawski J. Ouaknine B. Wachter and J. Worrell. 2013. On the Complexity of Equivalence and Minimisation for Q-weighted Automata. Logical Methods in Computer Science 9 (2013).","DOI":"10.2168\/LMCS-9(1:8)2013"},{"key":"e_1_3_2_1_32_1","volume-title":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 296\u2013310","author":"Kiefer S.","unstructured":"S. Kiefer and D. Wojtczak . 2011. On probabilistic parallel programs with process creation and synchronisation . In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 296\u2013310 . S. Kiefer and D. Wojtczak. 2011. On probabilistic parallel programs with process creation and synchronisation. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 296\u2013310."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1996.0019"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196718500431"},{"key":"e_1_3_2_1_35_1","volume-title":"Multiplicative Number Theory","author":"Montgomery H.","unstructured":"H.\u00a0Davenport\u00a0 H. L. and Montgomery . 2013. Multiplicative Number Theory . Springer New York . H.\u00a0Davenport\u00a0H. L. and Montgomery. 2013. Multiplicative Number Theory. Springer New York."},{"key":"e_1_3_2_1_36_1","volume-title":"Algebraic Number Fields","author":"Lagarias C.","unstructured":"J.\u00a0 C. Lagarias and A.\u00a0 M. Odlyzko . 1977. Effective versions of the Chebotarev density theorem . In Algebraic Number Fields . Academic Press , 409\u2013464. J.\u00a0C. Lagarias and A.\u00a0M. Odlyzko. 1977. Effective versions of the Chebotarev density theorem. In Algebraic Number Fields. Academic Press, 409\u2013464."},{"key":"e_1_3_2_1_37_1","volume-title":"International Symposium on Symbolic and Algebraic Computation","author":"Landau S.","year":"1984","unstructured":"S. Landau . 1984 . Polynomial Time Algorithms for Galois Groups. In EUROSAM 84 , International Symposium on Symbolic and Algebraic Computation , Cambridge, England, UK , July 9-11, 1984, Proceedings(Lecture Notes in Computer Science, Vol.\u00a0174), J.\u00a0P. Fitch (Ed.). Springer, 225\u2013236. S. Landau. 1984. Polynomial Time Algorithms for Galois Groups. In EUROSAM 84, International Symposium on Symbolic and Algebraic Computation, Cambridge, England, UK, July 9-11, 1984, Proceedings(Lecture Notes in Computer Science, Vol.\u00a0174), J.\u00a0P. Fitch (Ed.). Springer, 225\u2013236."},{"key":"e_1_3_2_1_38_1","volume-title":"2015 30th Annual ACM\/IEEE Symposium on Logic in Computer Science. IEEE, 667\u2013676","author":"Lechner A.","unstructured":"A. Lechner , J. Ouaknine , and J. Worrell . 2015. On the complexity of linear arithmetic with divisibility . In 2015 30th Annual ACM\/IEEE Symposium on Logic in Computer Science. IEEE, 667\u2013676 . A. Lechner, J. Ouaknine, and J. Worrell. 2015. On the complexity of linear arithmetic with divisibility. In 2015 30th Annual ACM\/IEEE Symposium on Logic in Computer Science. IEEE, 667\u2013676."},{"key":"e_1_3_2_1_39_1","volume-title":"The compressed word problem for groups","author":"Lohrey Markus","unstructured":"Markus Lohrey . 2014. The compressed word problem for groups . Springer . Markus Lohrey. 2014. The compressed word problem for groups. Springer."},{"key":"e_1_3_2_1_40_1","unstructured":"L. Lov\u00e1sz. 1979. On determinants matchings and random algorithms.. In FCT Vol.\u00a079. 565\u2013574. L. Lov\u00e1sz. 1979. On determinants matchings and random algorithms.. In FCT Vol.\u00a079. 565\u2013574."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"D. Richardson. 1992. The elementary constant problem. In Papers from the international symposium on Symbolic and algebraic computation. 108\u2013116. D. Richardson. 1992. The elementary constant problem. In Papers from the international symposium on Symbolic and algebraic computation. 108\u2013116.","DOI":"10.1145\/143242.143284"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1997.0157"},{"key":"e_1_3_2_1_43_1","volume-title":"Proceedings of the 15th Annual ACM Symposium on Theory of Computing","author":"Miller S.","year":"1983","unstructured":"S. and G.\u00a0L. Miller . 1983 . Solvability by Radicals is in Polynomial Time . In Proceedings of the 15th Annual ACM Symposium on Theory of Computing , 25-27 April, 1983, Boston, Massachusetts, USA. ACM, 140\u2013151. S. and G.\u00a0L. Miller. 1983. Solvability by Radicals is in Polynomial Time. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA. ACM, 140\u2013151."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698692"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"P. Stevenhagen H.\u00a0W. Lenstra and Jr.1995. Chebotarev and his density theorem. P. Stevenhagen H.\u00a0W. Lenstra and Jr.1995. Chebotarev and his density theorem.","DOI":"10.1007\/BF03027290"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"I. Stewart and D. Tall. 2001. Algebraic Number Theory and Fermat\u2019s Last Theorem: Third Edition. Taylor & Francis. I. Stewart and D. Tall. 2001. Algebraic Number Theory and Fermat\u2019s Last Theorem: Third Edition. Taylor & Francis.","DOI":"10.1201\/9781439864081"},{"key":"e_1_3_2_1_47_1","volume-title":"Galois theory","author":"Stewart N.","unstructured":"I.\u00a0 N. Stewart . 1973. Galois theory . Chapman and Hall . I.\u00a0N. Stewart. 1973. Galois theory. Chapman and Hall."},{"key":"e_1_3_2_1_48_1","volume-title":"International Conference on Concurrency Theory. Springer, 482\u2013496","author":"Ummels M.","unstructured":"M. Ummels and D. Wojtczak . 2011. The complexity of Nash equilibria in limit-average games . In International Conference on Concurrency Theory. Springer, 482\u2013496 . M. Ummels and D. Wojtczak. 2011. The complexity of Nash equilibria in limit-average games. In International Conference on Concurrency Theory. Springer, 482\u2013496."}],"event":{"name":"LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Haifa Israel","acronym":"LICS '22","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation"]},"container-title":["Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533331","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3533331","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:09Z","timestamp":1750186929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533331"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":48,"alternative-id":["10.1145\/3531130.3533331","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3533331","relation":{},"subject":[],"published":{"date-parts":[[2022,8,2]]},"assertion":[{"value":"2022-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}