Fast K\"otter-Nielsen-H{\o}holdt Interpolation in the Guruswami-Sudan   Algorithm
  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. 
Johan S. R. Nielsen
cs.IT cs.SC math.IT