Fast Kötter–Nielsen–Høholdt Interpolation in the Guruswami–Sudan Algorithm

Johan Sebastian Rosenkilde Nielsen

Research output: Contribution to conferencePaperResearchpeer-review

195 Downloads (Pure)

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 languageEnglish
Publication date2014
Number of pages6
Publication statusPublished - 2014
Externally publishedYes
Event14th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2014) - Svetlogorsk, Russian Federation
Duration: 7 Sep 201413 Sep 2014
Conference number: 14
http://acct2014.iitp.ru/

Workshop

Workshop14th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2014)
Number14
CountryRussian Federation
CitySvetlogorsk
Period07/09/201413/09/2014
Internet address

Bibliographical note

at the 14th International Workshop on Algebraic and Combinatorial Coding Theory

Fingerprint Dive into the research topics of 'Fast Kötter–Nielsen–Høholdt Interpolation in the Guruswami–Sudan Algorithm'. Together they form a unique fingerprint.

Cite this