Abstract
The Kötter-Nielsen-Hø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.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.