{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T01:43:02Z","timestamp":1758591782714,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,7,16]],"date-time":"2024-07-16T00:00:00Z","timestamp":1721088000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-15-IDEX-0002;ANR-21-CE39-0006;ANR-22-PECY-0010;22-PECY-003"],"award-info":[{"award-number":["ANR-15-IDEX-0002;ANR-21-CE39-0006;ANR-22-PECY-0010;22-PECY-003"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2217597"],"award-info":[{"award-number":["2217597"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,7,16]]},"DOI":"10.1145\/3666000.3669717","type":"proceedings-article","created":{"date-parts":[[2024,7,15]],"date-time":"2024-07-15T13:18:51Z","timestamp":1721049531000},"page":"437-446","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast interpolation and multiplication of unbalanced polynomials"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0489-5134","authenticated-orcid":false,"given":"Pascal","family":"Giorgi","sequence":"first","affiliation":[{"name":"LIRMM, CNRS, University of Montpellier, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2057-5429","authenticated-orcid":false,"given":"Bruno","family":"Grenet","sequence":"additional","affiliation":[{"name":"Laboratoire Jean Kuntzmann, CNRS, Université Grenoble Alpes, France"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-3559-131X","authenticated-orcid":false,"given":"Armelle","family":"Perret du Cray","sequence":"additional","affiliation":[{"name":"Symbolic Computation Group, University of Waterloo, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1408-6872","authenticated-orcid":false,"given":"Daniel S.","family":"Roche","sequence":"additional","affiliation":[{"name":"Computer Science Department, United States Naval Academy, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00032-8"},{"volume-title":"Sparse polynomial interpolation and testing. Ph.\u00a0D. Dissertation","author":"Arnold Andrew","key":"e_1_3_2_1_2_1","unstructured":"Andrew Arnold. 2016. Sparse polynomial interpolation and testing. Ph.\u00a0D. Dissertation. University of Waterloo."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608671"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2015.11.005"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608674"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755996.2756653"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62241"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2022.09.002"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608648"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAU.1970.1162132"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Marco Bodrato and Alberto Zanoni. 2020. Univariate Polynomials with Long Unbalanced Coefficients as Bivariate Balanced Ones: A Toom-Cook Multiplication Approach. In Computer Algebra in Scientific Computing Fran\u00e7ois Boulier Matthew England Timur\u00a0M. Sadykov and Evgenii\u00a0V. Vorozhtsov (Eds.). 91\u2013107. https:\/\/doi.org\/10.1007\/978-3-030-60026-6_6","DOI":"10.1007\/978-3-030-60026-6_6"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01178683"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SYNASC.2016.024"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509992"},{"key":"e_1_3_2_1_15_1","unstructured":"Stephen\u00a0A. Cook. 1966. On the Minimum Computation Time of Functions. Ph.\u00a0D. Dissertation. Harvard."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.050"},{"key":"e_1_3_2_1_17_1","volume-title":"Can You Save Time in Multiplying Polynomials by Encoding Them as Integers?","author":"Fateman J","year":"2010","unstructured":"Richard\u00a0J Fateman. 2010. Can You Save Time in Multiplying Polynomials by Encoding Them as Integers? (2010). https:\/\/people.eecs.berkeley.edu\/\u00a0fateman\/papers\/polysbyGMP.pdf."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.030"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993886.1993909"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373207.3404026"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2022.08.011"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3476446.3536173"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219073"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2021.193.2.4"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3505584"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3005344"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465506.2465526"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442829.2442861"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2733693.2733721"},{"key":"e_1_3_2_1_30_1","unstructured":"Joris van der Hoeven and Gr\u00e9goire Lecerf. 2019. Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields. (2019). https:\/\/hal.archives-ouvertes.fr\/hal-02382117 preprint."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466895.3466896"},{"key":"e_1_3_2_1_32_1","unstructured":"Joris van der Hoeven and Gr\u00e9goire Lecerf. 2023. Fast interpolation of sparse multivariate polynomials. arXiv:2312.17664."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1045"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326229.3326250"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11425-020-1791-5"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2022.06.002"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26831-2_15"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2019.10.005"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.36"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837210.1837233"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086837.1086847"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/96877.96912"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(03)00088-9"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21946"},{"key":"e_1_3_2_1_45_1","volume-title":"Proceedings of the 1988 international symposium on symbolic and algebraic computation(ISSAC\u201988)","author":"Kaltofen Erich","year":"1988","unstructured":"Erich Kaltofen and Lakshman Yagati. 1988. Improved sparse multivariate polynomial interpolation algorithms. In Proceedings of the 1988 international symposium on symbolic and algebraic computation(ISSAC\u201988), P.\u00a0Gianni (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 467\u2013474."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277548.1277577"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837210.1837213"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993886.1993916"},{"key":"e_1_3_2_1_49_1","volume-title":"Multiplication of Multidigit Numbers on Automata. Soviet Physics Doklady 7 (12","author":"Karatsuba Anatolii","year":"1962","unstructured":"Anatolii Karatsuba and Yu Ofman. 1962. Multiplication of Multidigit Numbers on Automata. Soviet Physics Doklady 7 (12 1962), 595."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1515\/crll.1882.92.1","article-title":"Grundz\u00fcge einer arithmetischen Theorie der algebraischen Gr\u00f6ssen","volume":"92","author":"Kronecker Leopold","year":"1882","unstructured":"Leopold Kronecker. 1882. Grundz\u00fcge einer arithmetischen Theorie der algebraischen Gr\u00f6ssen. Journal f\u00fcr die reine und angewandte Mathematik 92 (1882), 1\u2013122.","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3476446.3535495"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.03.003"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792239291"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1576702.1576739"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2010.08.014"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1996.0020"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2989385"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1980.1163372"},{"key":"e_1_3_2_1_59_1","unstructured":"Armelle Perret\u00a0du Cray. 2023. Algorithmes pour les polyn\u00f4mes creux: interpolation arithm\u00e9tique test d\u2019identit\u00e9. Ph.\u00a0D. Dissertation. L\u2019Universit\u00e9 de Montpellier."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-017-0370-5"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.3389\/fams.2016.00001"},{"key":"e_1_3_2_1_62_1","unstructured":"Gaspard Clair Fran\u00e7ois Marie Riche\u00a0de Prony. 1795. Essai exp\u00e9rimental et analytique sur les lois de la Dilatabilit\u00e9 de fluides \u00e9lastique et sur celles de la Force expansive de la vapeur de l\u2019eau et de la vapeur de l\u2019alkool \u00e0 diff\u00e9rentes temp\u00e9ratures. Journal \u00c9cole Polytechnique 1 Flor\u00e9al et Prairial III (1795) 24\u201376. https:\/\/gallica.bnf.fr\/ark:\/12148\/bpt6k433661n\/f32.item"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2010.08.013"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255631807"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-11607-9_1"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242355"},{"key":"e_1_3_2_1_67_1","first-page":"714","article-title":"The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers","volume":"3","author":"Toom L.","year":"1963","unstructured":"Andrei\u00a0L. Toom. 1963. The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers. Soviet Mathematics Doklady 3 (1963), 714\u2013716.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.12.009"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80018-1"}],"event":{"name":"ISSAC '24: International Symposium on Symbolic and Algebraic Computation","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Raleigh NC USA","acronym":"ISSAC '24"},"container-title":["Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3666000.3669717","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3666000.3669717","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T00:52:08Z","timestamp":1758588728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3666000.3669717"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,16]]},"references-count":70,"alternative-id":["10.1145\/3666000.3669717","10.1145\/3666000"],"URL":"https:\/\/doi.org\/10.1145\/3666000.3669717","relation":{},"subject":[],"published":{"date-parts":[[2024,7,16]]},"assertion":[{"value":"2024-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}