{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T21:18:45Z","timestamp":1774991925589,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"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,7,4]]},"DOI":"10.1145\/3476446.3536173","type":"proceedings-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T13:16:01Z","timestamp":1657026961000},"page":"459-468","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Sparse Polynomial Interpolation and Division in Soft-linear Time"],"prefix":"10.1145","author":[{"given":"Pascal","family":"Giorgi","sequence":"first","affiliation":[{"name":"LIRMM, Univ. Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Grenet","sequence":"additional","affiliation":[{"name":"LIRMM, Univ. Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armelle","family":"Perret du Cray","sequence":"additional","affiliation":[{"name":"LIRMM, Univ. Montpellier, CNRS, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel S.","family":"Roche","sequence":"additional","affiliation":[{"name":"United States Naval Academy, Annapolis, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2014-02919-0"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00032-8"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC'14)","author":"Arnold Andrew","unstructured":"Andrew Arnold , Mark Giesbrecht , and Daniel S. Roche . 2014. Sparse interpolation over finite fields via low-order roots of unity . In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC'14) . Association for Computing Machinery, 27--34. https:\/\/doi.org\/10.1145\/2608628.2608671 10.1145\/2608628.2608671 Andrew Arnold, Mark Giesbrecht, and Daniel S. Roche. 2014. Sparse interpolation over finite fields via low-order roots of unity. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC'14). Association for Computing Machinery, 27--34. https:\/\/doi.org\/10.1145\/2608628.2608671"},{"key":"e_1_3_2_1_5_1","volume-title":"Roche","author":"Arnold Andrew","year":"2015","unstructured":"Andrew Arnold , Mark Giesbrecht , and Daniel S . Roche . 2015 . Faster sparse multivariate polynomial interpolation of straight-line programs. Journal of Symbolic Computation ( 2015). https:\/\/doi.org\/10.1016\/j.jsc.2015.11.005 10.1016\/j.jsc.2015.11.005 Andrew Arnold, Mark Giesbrecht, and Daniel S. Roche. 2015. Faster sparse multivariate polynomial interpolation of straight-line programs. Journal of Symbolic Computation (2015). https:\/\/doi.org\/10.1016\/j.jsc.2015.11.005"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation","author":"Arnold Andrew","unstructured":"Andrew Arnold and Daniel S. Roche . 2015. Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication . In Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation ( Bath, United Kingdom) (ISSAC '15). ACM, 29--36. https:\/\/doi.org\/10.1145\/2755996.2756653 10.1145\/2755996.2756653 Andrew Arnold and Daniel S. Roche. 2015. Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication. In Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation (Bath, United Kingdom) (ISSAC '15). ACM, 29--36. https:\/\/doi.org\/10.1145\/2755996.2756653"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.09.029"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAU.1970.1162132"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608648"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/860854.860870"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.050"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1987.1057299"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.03.030"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2790282.2790285"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11. ACM Press","author":"Giesbrecht Mark","year":"1993","unstructured":"Mark Giesbrecht and Daniel S. Roche . 2011. Diversification improves interpolation . In Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11. ACM Press , San Jose, California, USA, 123. https:\/\/doi.org\/10.1145\/ 1993 886.1993909 10.1145\/1993886.1993909 Mark Giesbrecht and Daniel S. Roche. 2011. Diversification improves interpolation. In Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11. ACM Press, San Jose, California, USA, 123. https:\/\/doi.org\/10.1145\/1993886.1993909"},{"key":"e_1_3_2_1_17_1","volume-title":"Armelle Perret du Cray, and Daniel S. Roche","author":"Giorgi Pascal","year":"2022","unstructured":"Pascal Giorgi , Bruno Grenet , Armelle Perret du Cray, and Daniel S. Roche . 2022 . Random primes in arithmetic progressions. arXiv:2202.05955. Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray, and Daniel S. Roche. 2022. Random primes in arithmetic progressions. arXiv:2202.05955."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373207.3404026"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452143.3465539"},{"key":"e_1_3_2_1_20_1","volume-title":"Polynomial modular product verification and its implications. Journal of Symbolic Computation","author":"Giorgi Pascal","year":"2022","unstructured":"Pascal Giorgi , Bruno Grenet , and Armelle Perret du Cray . 2022. Polynomial modular product verification and its implications. Journal of Symbolic Computation ( 2022 ), to appear. Pascal Giorgi, Bruno Grenet, and Armelle Perret du Cray. 2022. Polynomial modular product verification and its implications. Journal of Symbolic Computation (2022), to appear."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219073"},{"key":"e_1_3_2_1_22_1","unstructured":"Joris van der Hoeven. 2020. Probably faster multiplication of sparse polynomials. (2020). https:\/\/hal.archives-ouvertes.fr\/hal-02473830 technical report.  Joris van der Hoeven. 2020. Probably faster multiplication of sparse polynomials. (2020). https:\/\/hal.archives-ouvertes.fr\/hal-02473830 technical report."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2733693.2733721"},{"key":"e_1_3_2_1_24_1","unstructured":"Joris van der Hoeven and Gr\u00e9goire Lecerf. 2019. Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields. (2019). https:\/\/hal.archivesouvertes. fr\/hal-02382117 technical report.  Joris van der Hoeven and Gr\u00e9goire Lecerf. 2019. Sparse polynomial interpolation. Exploring fast heuristic algorithms over finite fields. (2019). https:\/\/hal.archivesouvertes. fr\/hal-02382117 technical report."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466895.3466896"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1045"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326229.3326250"},{"key":"e_1_3_2_1_28_1","unstructured":"Qiao-Long Huang. 2020. Sparse Polynomial Interpolation Based on Derivative. (2020). http:\/\/arxiv.org\/abs\/2002.03708  Qiao-Long Huang. 2020. Sparse Polynomial Interpolation Based on Derivative. (2020). http:\/\/arxiv.org\/abs\/2002.03708"},{"key":"e_1_3_2_1_29_1","volume-title":"Sparse polynomial interpolation based on diversification. Science China Mathematics","author":"Huang Qiao-Long","year":"2021","unstructured":"Qiao-Long Huang . 2021. Sparse polynomial interpolation based on diversification. Science China Mathematics ( 2021 ). https:\/\/doi.org\/10.1007\/s11425-020--1791--5 10.1007\/s11425-020--1791--5 Qiao-Long Huang. 2021. Sparse polynomial interpolation based on diversification. Science China Mathematics (2021). https:\/\/doi.org\/10.1007\/s11425-020--1791--5"},{"key":"e_1_3_2_1_30_1","volume-title":"Computer Algebra in Scientific Computing","author":"Huang Qiao-Long","unstructured":"Qiao-Long Huang and Xiao-Shan Gao . 2019. Revisit Sparse Polynomial Interpolation Based on Randomized Kronecker Substitution . In Computer Algebra in Scientific Computing . Springer International Publishing , 215--235. https: \/\/doi.org\/10.1007\/978--3-030--26831--2_15 10.1007\/978--3-030--26831--2_15 Qiao-Long Huang and Xiao-Shan Gao. 2019. Revisit Sparse Polynomial Interpolation Based on Randomized Kronecker Substitution. In Computer Algebra in Scientific Computing. Springer International Publishing, 215--235. https: \/\/doi.org\/10.1007\/978--3-030--26831--2_15"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2019.10.005"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837210.1837233"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086837.1086847"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(03)00088-9"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837210.1837213"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/96877.96912"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the 36th international symposium on Symbolic and algebraic computation. Association for Computing Machinery","author":"Erich","year":"1993","unstructured":"Erich L. Kaltofen and Michael Nehring. 2011. Supersparse black box rational function interpolation . In Proceedings of the 36th international symposium on Symbolic and algebraic computation. Association for Computing Machinery , New York, NY, USA, 177--186. https:\/\/doi.org\/10.1145\/ 1993 886.1993916 10.1145\/1993886.1993916 Erich L. Kaltofen and Michael Nehring. 2011. Supersparse black box rational function interpolation. In Proceedings of the 36th international symposium on Symbolic and algebraic computation. Association for Computing Machinery, New York, NY, USA, 177--186. https:\/\/doi.org\/10.1145\/1993886.1993916"},{"key":"e_1_3_2_1_38_1","volume-title":"Kaltofen and Lakshman Yagati","author":"Erich","year":"1988","unstructured":"Erich L. Kaltofen and Lakshman Yagati . 1988 . Improved Sparse Multivariate Polynomial Interpolation Algorithms. In Symbolic and Algebraic Computation. Springer Berlin Heidelberg , 467--474. https:\/\/doi.org\/10.1007\/3--540--51084--2_44 10.1007\/3--540--51084--2_44 Erich L. Kaltofen and Lakshman Yagati. 1988. Improved Sparse Multivariate Polynomial Interpolation Algorithms. In Symbolic and Algebraic Computation. Springer Berlin Heidelberg, 467--474. https:\/\/doi.org\/10.1007\/3--540--51084--2_44"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 2007 international symposium on Symbolic and algebraic computation (ISSAC '07)","author":"Erich","unstructured":"Erich L. Kaltofen and Zhengfeng Yang. 2007. On exact and approximate interpolation of sparse rational functions . In Proceedings of the 2007 international symposium on Symbolic and algebraic computation (ISSAC '07) . ACM Press, Waterloo, Ontario, Canada, 203. https:\/\/doi.org\/10.1145\/1277548.1277577 10.1145\/1277548.1277577 Erich L. Kaltofen and Zhengfeng Yang. 2007. On exact and approximate interpolation of sparse rational functions. In Proceedings of the 2007 international symposium on Symbolic and algebraic computation (ISSAC '07). ACM Press, Waterloo, Ontario, Canada, 203. https:\/\/doi.org\/10.1145\/1277548.1277577"},{"key":"e_1_3_2_1_40_1","first-page":"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 -- 122 . Leopold Kronecker. 1882. Grundz\u00fcge einer arithmetischen Theorie der algebraischen Gr\u00f6ssen. Journal f\u00fcr die reine und angewandte Mathematik 92 (1882), 1--122.","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792239291"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75187-8_23"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1576702.1576739"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2010.08.014"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1996.0020"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2989385"},{"key":"e_1_3_2_1_47_1","volume-title":"Advances in Cryptology -- EUROCRYPT '99 (Lecture Notes in Computer Science)","author":"Paillier Pascal","unstructured":"Pascal Paillier . 1999. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes . In Advances in Cryptology -- EUROCRYPT '99 (Lecture Notes in Computer Science) , Jacques Stern (Ed.). Springer , Berlin, Heidelberg , 223--238. https:\/\/doi.org\/10.1007\/3--540--48910-X_16 10.1007\/3--540--48910-X_16 Pascal Paillier. 1999. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In Advances in Cryptology -- EUROCRYPT '99 (Lecture Notes in Computer Science), Jacques Stern (Ed.). Springer, Berlin, Heidelberg, 223--238. https:\/\/doi.org\/10.1007\/3--540--48910-X_16"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3208976.3209027"},{"key":"e_1_3_2_1_49_1","volume-title":"Estimations du type Brun-Titchmarsh. Groupe d'\u00e9tude en th\u00e9orie analytique des nombres 1, 37","author":"Rousselet Bruno","year":"1985","unstructured":"Bruno Rousselet . 1985. Estimations du type Brun-Titchmarsh. Groupe d'\u00e9tude en th\u00e9orie analytique des nombres 1, 37 ( 1985 ), 1. Bruno Rousselet. 1985. Estimations du type Brun-Titchmarsh. Groupe d'\u00e9tude en th\u00e9orie analytique des nombres 1, 37 (1985), 1."},{"key":"e_1_3_2_1_50_1","volume-title":"Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica 1 (06","author":"Sch\u00f6nhage Arnold","year":"1971","unstructured":"Arnold Sch\u00f6nhage . 1971. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica 1 (06 1971 ), 139--144. https:\/\/doi.org\/10.1007\/BF00289520 10.1007\/BF00289520 Arnold Sch\u00f6nhage. 1971. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica 1 (06 1971), 139--144. https:\/\/doi.org\/10.1007\/BF00289520"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5802\/pmb.24"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80018-1"}],"event":{"name":"ISSAC '22: International Symposium on Symbolic and Algebraic Computation","location":"Villeneuve-d'Ascq France","acronym":"ISSAC '22","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"]},"container-title":["Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3536173","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476446.3536173","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:19Z","timestamp":1750268959000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476446.3536173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,4]]},"references-count":51,"alternative-id":["10.1145\/3476446.3536173","10.1145\/3476446"],"URL":"https:\/\/doi.org\/10.1145\/3476446.3536173","relation":{},"subject":[],"published":{"date-parts":[[2022,7,4]]},"assertion":[{"value":"2022-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}