Fast K\"otter-Nielsen-H{o}holdt Interpolation in the Guruswami-Sudan Algorithm
classification
💻 cs.IT
cs.SCmath.IT
keywords
algorithmguruswami-sudanholdtinterpolationotter-nielsen-hspeed-upasymptoticbivariate
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.