Sub-quadratic decoding of one-point hermitian codes

Johan Sebastian Rosenkilde Nielsen, Peter Beelen

Research output: Contribution to journalJournal articleResearchpeer-review

265 Downloads (Pure)


We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realization of the Guruswami-Sudan algorithm using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimization. The second is a power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the matrix minimization algorithms from computer algebra, yielding similar asymptotic complexities.
Original languageEnglish
JournalIEEE Transactions on Information Theory
Issue number6
Pages (from-to)3225-3240
Publication statusPublished - 2015

Bibliographical note

Copyright 2015 IEEE. IEEE. Personal use of this material is permitted. Permission
from IEEE must be obtained for all other uses, in any current or future media, including reprinting /republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.


  • Hermitian codes
  • AG codes
  • list decoding
  • Guruswami–Sudan
  • power decoding

Fingerprint Dive into the research topics of 'Sub-quadratic decoding of one-point hermitian codes'. Together they form a unique fingerprint.

Cite this