Some gabidulin codes cannot be list decoded efficiently at any radius

Netanel Raviv, Antonia Wachter-Zeh

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


Gabidulin codes can be seen as the rank-metric equivalent of Reed-Solomon codes. It was recently proved, using subspace polynomials, that Gabidulin codes cannot be list decoded beyond the so-called Johnson radius. In another result, cyclic subspace codes were constructed by inspecting the connection between subspaces and their subspace polynomials. In this paper, these subspace codes are used to prove two bounds on the list size in decoding certain Gabidulin codes. The first bound is an existential one, showing that exponentially sized lists exist for codes with specific parameters. The second bound presents exponentially sized lists explicitly for a different set of parameters. Both bounds rule out the possibility of efficiently list decoding several families of Gabidulin codes for any radius beyond half the minimum distance. Such a result was known so far only for non-linear rank-metric codes, and not for Gabidulin codes. Using a standard operation called lifting, identical results also follow for an important class of constant dimension subspace codes.

Original languageEnglish
Article number7414489
Pages (from-to)1605-1615
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number4
StatePublished - Apr 2016
Externally publishedYes


  • Gabidulin codes
  • Rank-metric codes
  • list decoding
  • subspace codes
  • subspace polynomials


Dive into the research topics of 'Some gabidulin codes cannot be list decoded efficiently at any radius'. Together they form a unique fingerprint.

Cite this