标题： 快速郭德纳-尼尔森-霍尔德特插值在古鲁斯瓦米-苏丹算法中 显示英文标题

标题： Fast Kötter-Nielsen-Høholdt Interpolation in the Guruswami-Sudan Algorithm

摘要： Kötter-Nielsen-H{\o }算法是构造 Reed-Solomon 码在 Guruswami-Sudan 解码算法中的二元插值多项式的一种常用方法。 在本文中，我们展示了如何使用分治技术来提供该算法的渐近加速，使其复杂度在 n 上接近线性。我们的一些观察结果也可以为该算法的经典版本提供实际的加速。 显示英文摘要

摘要： The K\"otter-Nielsen-H{\o}holdt algorithm is a popular way to construct the bivariate interpolation polynomial in the Guruswami-Sudan decoding algorithm for Reed-Solomon codes. In this paper, we show how one can use Divide & Conquer techniques to provide an asymptotic speed-up of the algorithm, rendering its complexity quasi-linear in n. Several of our observations can also provide a practical speed-up to the classical version of the algorithm.