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

Johan Sebastian Rosenkilde Nielsen

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

Johan Sebastian Rosenkilde Nielsen

Ulm University

Research output: Contribution to conference › Paper › Research › peer-review

343 Downloads (Orbit)

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	http://acct2014.iitp.ru/

Bibliographical note

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

Access to Document

2014 acct fast knhFinal published version, 259 KB

OpenUrl availability

Check availability in DTU Findit

Cite this

@conference{01dbadce7011428d866aeefeee0733b6,

title = "Fast K{\"o}tter{\textendash}Nielsen{\textendash}H{\o}holdt Interpolation in the Guruswami{\textendash}Sudan Algorithm",

abstract = "The K{\"o}tter-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.",

author = "Nielsen, \{Johan Sebastian Rosenkilde\}",

note = "at the 14th International Workshop on Algebraic and Combinatorial Coding Theory; 14th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2014), ACCT ; Conference date: 07-09-2014 Through 13-09-2014",

year = "2014",

language = "English",

url = "http://acct2014.iitp.ru/",

}

TY - CONF

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

AU - Nielsen, Johan Sebastian Rosenkilde

N1 - Conference code: 14

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

M3 - Paper

T2 - 14th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT 2014)

Y2 - 7 September 2014 through 13 September 2014

ER -

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

Abstract

Workshop

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this