[日時] 2024年10月18日(金) 12:20--13:20
[場所] 東京大学 本郷キャンパス 工14号館 534室
[講演者] 木ノ下 恭範 (東京工業大学)
[題目(Title)] Power Series Composition in Near-Linear Time
[概要(Abstract)]
We present an algebraic algorithm that computes the composition of two power series in softly linear time complexity. The previous best algorithms are O(n^{1+o(1)}) non-algebraic algorithm by Kedlaya and Umans (FOCS 2008) and an O(n^1.43) algebraic algorithm by Neiger, Salvy, Schost and Villard (JACM 2023). Our algorithm builds upon the recent Graeffe iteration approach to manipulate rational power series introduced by Bostan and Mori (SOSA 2021). Moreover, this algorithm operates on commutative rings, which are more general than fields.
Since the algorithm is relatively simple, I expect to be able to fully explain it in this talk. This is a joint work with Baitian Li, which will appear in FOCS 2024.