{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:24Z","timestamp":1750309164601,"version":"3.41.0"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T00:00:00Z","timestamp":1712707200000},"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":["J. ACM"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>\n            A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by\u00a0\n            <jats:italic>n<\/jats:italic>\n            , the algorithm uses\u00a0\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.43<\/jats:sup>\n            ) field operations, breaking through the 3\/2 barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require\u00a0\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.63<\/jats:sup>\n            ) field operations in general, and\u00a0\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              3\/2+\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in\u00a0\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              5\/3+\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            operations, while previous ones run in\u00a0\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) operations.\n          <\/jats:p>\n          <jats:p>Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation.<\/jats:p>","DOI":"10.1145\/3638349","type":"journal-article","created":{"date-parts":[[2023,12,25]],"date-time":"2023-12-25T11:39:28Z","timestamp":1703504368000},"page":"1-79","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Faster Modular Composition"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8311-9490","authenticated-orcid":false,"given":"Vincent","family":"Neiger","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4313-0679","authenticated-orcid":false,"given":"Bruno","family":"Salvy","sequence":"additional","affiliation":[{"name":"Inria, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8638-9357","authenticated-orcid":false,"given":"\u00c9ric","family":"Schost","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1936-7155","authenticated-orcid":false,"given":"Gilles","family":"Villard","sequence":"additional","affiliation":[{"name":"CNRS, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,10]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373207.3404053"},{"key":"e_1_3_2_3_2","volume-title":"Efficient Computation of Riemann-Roch Spaces for Plane Curves with Ordinary Singularities","author":"Abelard Simon","year":"2021","unstructured":"Simon Abelard, Alain Couvreur, and Gr\u00e9goire Lecerf. 2021. Efficient Computation of Riemann-Roch Spaces for Plane Curves with Ordinary Singularities. HAL Report hal-03110135. Retrieved from https:\/\/hal.archives-ouvertes.fr\/hal-03110135"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892230031"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/309831.309929"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1998.0216"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00028"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519968"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0265-3"},{"key":"e_1_3_2_11_2","volume-title":"Algorithmes Efficaces en Calcul Formel","author":"Bostan Alin","year":"2017","unstructured":"Alin Bostan, Fr\u00e9d\u00e9ric Chyzak, Marc Giusti, Romain Lebreton, Gr\u00e9goire Lecerf, Bruno Salvy, and \u00c9ric Schost. 2017. Algorithmes Efficaces en Calcul Formel. In French. Edited by the authors. Retrieved from https:\/\/hal.archives-ouvertes.fr\/AECF\/"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283492"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2005.07.001"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/860854.860870"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1390768.1390806"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90013-9"},{"key":"e_1_3_2_17_2","first-page":"149","volume-title":"Proc. Conference on Theoretical Computer Science (Waterloo ON, August 15\u201317, 1977)","author":"Brent Richard P.","year":"1977","unstructured":"Richard P. Brent and H. T. Kung. 1977. Fast algorithms for composition and reversion of multivariate power series. In Proc. Conference on Theoretical Computer Science (Waterloo ON, August 15\u201317, 1977). University of Waterloo, 149\u2013158."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322099"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022468019197"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.2307\/2153413"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15984-3_279"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00130"},{"key":"e_1_3_2_24_2","volume-title":"Abstract Algebra","author":"Dummit David S.","year":"2003","unstructured":"David S. Dummit and Richard M. Foote. 2003. Abstract Algebra. John Wiley & Sons."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1277548.1277569"},{"key":"e_1_3_2_26_2","first-page":"101","volume-title":"Proc. Mathematics of Surfaces II","author":"Gasca Mariano","year":"1987","unstructured":"Mariano Gasca and Jos\u00e9 J. Mart\u00ednez. 1987. On the computation of multivariate confluent Vandermonde determinants and its applications. In Proc. Mathematics of Surfaces II. Vol. 11. Oxford Univ. Press, 101\u2013114."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139856065"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01272074"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/b104035"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01613611"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-020-00204-9"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/860854.860889"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2002.0562"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-019-00389-9"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087634"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2018.05.002"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2019.03.002"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2020.101498"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3452143.3465531"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2021.101574"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2020.101499"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1998.0476"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2019.07.011"},{"key":"e_1_3_2_44_2","volume-title":"Linear Systems","author":"Kailath Thomas","year":"1980","unstructured":"Thomas Kailath. 1980. Linear Systems. Prentice-Hall."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/143242.143350"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2000.0370"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/113379.113396"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54522-0_93"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258777"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-98-00944-2"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0185-3"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/2500122"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/08073408X"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2017.03.003"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(85)80035-3"},{"key":"e_1_3_2_56_2","volume-title":"Faster Rectangular Matrix Multiplication by Combination Loss Analysis","author":"Gall Fran\u00e7ois Le","year":"2023","unstructured":"Fran\u00e7ois Le Gall. 2023. Faster Rectangular Matrix Multiplication by Combination Loss Analysis. arXiv:2307.06535. Retrieved from https:\/\/arxiv.org\/abs\/cs\/2307.06535"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.67"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-008-0062-4"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/800205.806344"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(02)00139-6"},{"key":"e_1_3_2_61_2","volume-title":"Bases of relations in one or several variables: fast algorithms and applications","author":"Neiger Vincent","year":"2016","unstructured":"Vincent Neiger. 2016. Bases of relations in one or several variables: fast algorithms and applications. Ph.D. Dissertation. \u00c9cole Normale Sup\u00e9rieure de Lyon. Retrieved from https:\/\/tel.archives-ouvertes.fr\/tel-01431413\/"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373207.3404032"},{"key":"e_1_3_2_63_2","volume-title":"Integral Matrices","author":"Newman Morris","year":"1972","unstructured":"Morris Newman. 1972. Integral Matrices. Academic Press. First edition."},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_49"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202007"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0063-y"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2012.05.008"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/258726.258792"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90107-6"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1994.1025"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1995.1055"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/309831.309859"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374445"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02141952"},{"key":"e_1_3_2_75_2","volume-title":"A study of Coppersmith\u2019s Block Wiedemann Algorithm using Matrix Polynomials","author":"Villard Gilles","year":"1997","unstructured":"Gilles Villard. 1997. A study of Coppersmith\u2019s Block Wiedemann Algorithm using Matrix Polynomials. RR 975 IM IMAG. Retrieved from http:\/\/perso.ens-lyon.fr\/gilles.villard\/BIBLIOGRAPHIE\/PDF\/rr0497.pdf"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1145\/3208976.3209020"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1986.1057137"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.134"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6392-0"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.12.009"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1145\/2442829.2442881"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3638349","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3638349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:53:35Z","timestamp":1750287215000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3638349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,10]]},"references-count":80,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3638349"],"URL":"https:\/\/doi.org\/10.1145\/3638349","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2024,4,10]]},"assertion":[{"value":"2021-10-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}