Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One
Abstract
Fix a prime power q. We prove that deciding whether a received word y in Fnqm lies at rank distance at most n-2 from the one-dimensional Gabidulin code {{λ.g : λ in Fqm } is NP-complete. Thus maximum-likelihood decoding of Gabidulin codes is NP-hard even for k = 1, an analogue of the Guruswami-Vardy theorem for Reed-Solomon codes. In the Hamming metric, by contrast, hardness at this radius requires the dimension to grow with the length, as in the Guruswami-Vardy theorem. The reduction is deterministic; consequently Rank Syndrome Decoding (RSD) and Rank Minimum Distance (RMD) for Fqm -linear codes are NP-complete under deterministic polynomial reductions, whereas the previously known reduction was randomized. The proof goes through a pivot problem that we introduce, Twisted Square Membership (TSM): given Fq-subspaces U, W in FqN , decide whether some non-zero a in U satisfies a^(q+1) in W . Quadratic systems in d unknowns are encoded into TSM, then TSM into Gabidulin decoding. The last step views the received word as an Fq-linear map and decoding at radius n - 2 as the search for an Fq-plane on which it acts as a scalar. With support U + τ W in a cubic extension and map a + τ b to a^(q^2) + τ bq^q , two Frobenius twists force solution planes to encode the relation a^(q+1) in W . All constructions are explicit and polynomial, with N = O(qd^2 ), n less than N + d, and m = 3N .
Related
- Constant-time decoding of Gabidulin codes and their generalizations with application to RQC
- Insdel Decoding Algorithms for Maximum Distance Separable Codes
- Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes
- Proximity Gaps for Gabidulin Codes and Applications
- Restricted Maximum Likelihood Estimation in Generalized Linear Mixed Models
BibTeX
@misc{gaborit2026maximumlikelihood,
title = {{Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One}},
author = {Philippe Gaborit},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34404},
eprint = {2610.34404},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34404},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One
AU - Philippe Gaborit
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34404
UR - https://arxiv.org/abs/2610.34404
AB - Fix a prime power q. We prove that deciding whether a received word y in Fnqm lies at rank distance at most n-2 from the one-dimensional Gabidulin code {{λ.g : λ in Fqm } is NP-complete. Thus maximum-likelihood decoding of Gabidulin codes is NP-hard even for k = 1, an analogue of the Guruswami-Vardy theorem for Reed-Solomon codes. In the Hamming metric, by contrast, hardness at this radius requires the dimension to grow with the length, as in the Guruswami-Vardy theorem. The reduction is deterministic; consequently Rank Syndrome Decoding (RSD) and Rank Minimum Distance (RMD) for Fqm -linear codes are NP-complete under deterministic polynomial reductions, whereas the previously known reduction was randomized. The proof goes through a pivot problem that we introduce, Twisted Square Membership (TSM): given Fq-subspaces U, W in FqN , decide whether some non-zero a in U satisfies a^(q+1) in W . Quadratic systems in d unknowns are encoded into TSM, then TSM into Gabidulin decoding. The last step views the received word as an Fq-linear map and decoding at radius n - 2 as the search for an Fq-plane on which it acts as a scalar. With support U + τ W in a cubic extension and map a + τ b to a^(q^2) + τ bq^q , two Frobenius twists force solution planes to encode the relation a^(q+1) in W . All constructions are explicit and polynomial, with N = O(qd^2 ), n less than N + d, and m = 3N .
ER -