{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T17:13:31Z","timestamp":1783617211825,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,12]],"date-time":"2026-07-12T00:00:00Z","timestamp":1783814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,13]]},"DOI":"10.1145\/3815436.3815465","type":"proceedings-article","created":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T16:11:51Z","timestamp":1783613511000},"page":"191-200","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Decomposition of Sparse Polynomials"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-9312-8768","authenticated-orcid":false,"given":"Mark","family":"Giesbrecht","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3405-7155","authenticated-orcid":false,"given":"Pascal","family":"Koiran","sequence":"additional","affiliation":[{"name":"ENS de Lyon, CNRS, Universit\u00e9 Claude Bernard Lyon 1, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3822-9746","authenticated-orcid":false,"given":"Saiyue","family":"Lyu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of British Columbia, Vancouver, British Columbia, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1408-6872","authenticated-orcid":false,"given":"Daniel","family":"Roche","sequence":"additional","affiliation":[{"name":"Computer Science Department, United States Naval Academy, Annapolis, Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,12]]},"reference":[{"key":"e_1_3_3_1_2_2","doi-asserted-by":"publisher","unstructured":"Sergei\u00a0A. Abramov. 2000. m-Sparse Solutions of Linear Ordinary Differential Equations with Polynomial Coefficients. Discrete Mathematics 217 1\u20133 (2000) 3\u201315. 10.1016\/S0012-365X(99)00252-6","DOI":"10.1016\/S0012-365X(99)00252-6"},{"key":"e_1_3_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087608"},{"key":"e_1_3_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/800205.806356"},{"key":"e_1_3_3_1_5_2","doi-asserted-by":"publisher","unstructured":"J\u00e9r\u00e9my Berthomieu Joris van\u00a0der Hoeven and Gr\u00e9goire Lecerf. 2011. Relaxed algorithms for p-adic numbers. Journal de th\u00e9orie des nombres de Bordeaux 23 3 (2011) 541\u2013577. 10.5802\/jtnb.777","DOI":"10.5802\/jtnb.777"},{"key":"e_1_3_3_1_6_2","doi-asserted-by":"publisher","unstructured":"Stephen\u00a0D. Cohen. 1972. Uniform Distribution of Polynomials over Finite Fields. Journal of the London Mathematical Society 6 1 (1972) 93\u2013102. 10.1112\/jlms\/s2-6.1.93","DOI":"10.1112\/jlms\/s2-6.1.93"},{"key":"e_1_3_3_1_7_2","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and J. Davenport. 1991. Polynomials whose powers are sparse. Acta Arith. 58 1 (1991) 79\u201387. http:\/\/matwbn.icm.edu.pl\/ksiazki\/aa\/aa58\/aa5816.pdf","DOI":"10.4064\/aa-58-1-79-87"},{"key":"e_1_3_3_1_8_2","unstructured":"Daniele Dona. 2015. On Lacunary Polynomials and a Generalization of Schinzel\u2019s Conjecture. Master\u2019s thesis. Concordia University and Universit\u00e9 de Bordeaux. https:\/\/spectrum.library.concordia.ca\/id\/eprint\/980332\/1\/Dona_MSc_F2015.pdf"},{"key":"e_1_3_3_1_9_2","unstructured":"Paul Erd\u0151s. 1949. On the Number of Terms of the Square of a Polynomial. Nieuw Archief voor Wiskunde (2) 23 (1949) 63\u201365. https:\/\/users.renyi.hu\/\u00a0p_erdos\/1949-08.pdf"},{"key":"e_1_3_3_1_10_2","doi-asserted-by":"publisher","unstructured":"Michael Fried. 1970. On a Conjecture of Schur. Michigan Mathematical Journal 17 1 (1970) 41\u201355. 10.1307\/mmj\/1029000374","DOI":"10.1307\/mmj\/1029000374"},{"key":"e_1_3_3_1_11_2","doi-asserted-by":"publisher","unstructured":"Mark Giesbrecht and Daniel\u00a0S. Roche. 2011. Detecting Lacunary Perfect Powers and Computing Their Roots. Journal of Symbolic Computation 46 11 (2011) 1242\u20131259. 10.1016\/j.jsc.2011.08.006","DOI":"10.1016\/j.jsc.2011.08.006"},{"key":"e_1_3_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1073884.1073914"},{"key":"e_1_3_3_1_13_2","doi-asserted-by":"publisher","unstructured":"Erich Kaltofen and Wen-shin Lee. 2003. Early Termination in Sparse Interpolation Algorithms. Journal of Symbolic Computation 36 3\u20134 (2003) 365\u2013400. 10.1016\/S0747-7171(03)00088-9","DOI":"10.1016\/S0747-7171(03)00088-9"},{"key":"e_1_3_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46796-3_47"},{"key":"e_1_3_3_1_15_2","doi-asserted-by":"publisher","unstructured":"Dexter Kozen and Susan Landau. 1989. Polynomial Decomposition Algorithms. Journal of Symbolic Computation 7 5 (1989) 445\u2013456. 10.1016\/S0747-7171(89)80027-6","DOI":"10.1016\/S0747-7171(89)80027-6"},{"key":"e_1_3_3_1_16_2","unstructured":"Saiyue Lyu. 2022. Faster Algorithms for Sparse Decomposition and Sparse Series Solutions to Differential Equations. Master\u2019s thesis. University of Waterloo. https:\/\/uwspace.uwaterloo.ca\/items\/ce984cb9-4838-44dc-ae73-d9a5dde33e4a"},{"key":"e_1_3_3_1_17_2","doi-asserted-by":"publisher","unstructured":"David\u00a0A. Plaisted. 1977. Sparse Complex Polynomials and Polynomial Reducibility. J. Comput. System Sci. 14 2 (1977) 210\u2013221. 10.1016\/S0022-0000(77)80013-5","DOI":"10.1016\/S0022-0000(77)80013-5"},{"key":"e_1_3_3_1_18_2","doi-asserted-by":"publisher","unstructured":"Joseph\u00a0F. Ritt. 1922. Prime and Composite Polynomials. Trans. Amer. Math. Soc. 23 1 (1922) 51\u201366. 10.1090\/S0002-9947-1922-1501189-9","DOI":"10.1090\/S0002-9947-1922-1501189-9"},{"key":"e_1_3_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3208976.3209027"},{"key":"e_1_3_3_1_20_2","doi-asserted-by":"publisher","unstructured":"Andrzej Schinzel. 1987. On the Number of Terms of a Power of a Polynomial. Acta Arithmetica 49 1 (1987) 55\u201370. 10.4064\/aa-49-1-55-70","DOI":"10.4064\/aa-49-1-55-70"},{"key":"e_1_3_3_1_21_2","doi-asserted-by":"publisher","unstructured":"Jacob\u00a0T. Schwartz. 1980. Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. ACM 27 4 (1980) 701\u2013717. 10.1145\/322217.322225","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_3_1_22_2","volume-title":"FLINT: Fast Library for Number Theory","author":"team The FLINT","year":"2025","unstructured":"The FLINT team. 2025. FLINT: Fast Library for Number Theory. https:\/\/flintlib.org Version 3.3.1."},{"key":"e_1_3_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.8042260"},{"key":"e_1_3_3_1_24_2","doi-asserted-by":"publisher","unstructured":"Gerhard Turnwald. 1995. On Schur\u2019s Conjecture. Journal of the Australian Mathematical Society 58 3 (1995) 312\u2013357. 10.1017\/S1446788700038349","DOI":"10.1017\/S1446788700038349"},{"key":"e_1_3_3_1_25_2","doi-asserted-by":"publisher","unstructured":"Joris van\u00a0der Hoeven. 2002. Relax but Don\u2019t Be Too Lazy. Journal of Symbolic Computation 34 6 (2002) 479\u2013542. 10.1006\/jsco.2002.0562","DOI":"10.1006\/jsco.2002.0562"},{"key":"e_1_3_3_1_26_2","doi-asserted-by":"publisher","unstructured":"Joachim von\u00a0zur Gathen. 1990. Functional Decomposition of Polynomials: The Tame Case. Journal of Symbolic Computation 9 3 (1990) 281\u2013299. 10.1016\/S0747-7171(08)80014-4","DOI":"10.1016\/S0747-7171(08)80014-4"},{"key":"e_1_3_3_1_27_2","doi-asserted-by":"publisher","unstructured":"Umberto Zannier. 2008. On Composite Lacunary Polynomials and the Proof of a Conjecture of Schinzel. Inventiones Mathematicae 174 1 (2008) 127\u2013138. 10.1007\/s00222-008-0136-8","DOI":"10.1007\/s00222-008-0136-8"}],"event":{"name":"ISSAC '26: 51st International Symposium on Symbolic and Algebraic Computation","location":"Oldenburg , Germany","acronym":"ISSAC '26"},"container-title":["Proceedings of the 2026 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"deposited":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T16:23:39Z","timestamp":1783614219000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3815436.3815465"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,12]]},"references-count":26,"alternative-id":["10.1145\/3815436.3815465","10.1145\/3815436"],"URL":"https:\/\/doi.org\/10.1145\/3815436.3815465","relation":{},"subject":[],"published":{"date-parts":[[2026,7,12]]},"assertion":[{"value":"2026-07-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}