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.
Original language | English |
---|---|
Publication date | 2014 |
Number of pages | 6 |
Publication status | Published - 2014 |
Externally published | Yes |
Event | 14th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2014) - Svetlogorsk, Russian Federation Duration: 7 Sept 2014 → 13 Sept 2014 Conference number: 14 http://acct2014.iitp.ru/ |
Workshop
Workshop | 14th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2014) |
---|---|
Number | 14 |
Country/Territory | Russian Federation |
City | Svetlogorsk |
Period | 07/09/2014 → 13/09/2014 |
Internet address |