Metraipolis › archive › dc_47c4cfbc478b
On the NP-Hardness of Rank-Metric Minimum Distance and Syndrome Decoding, at Every Rate — arXiv:2610.40825
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.40825
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T08:24:22.681Z
- SHA-256 of the archived text
c1e85cdf8308a67ed60341e3cff95815cf7e652d7b4ac1ed8944e15644825c35- Stable URL of this page
https://metraipolis.com/documento/dc_47c4cfbc478b
How to cite
On the NP-Hardness of Rank-Metric Minimum Distance and Syndrome Decoding, at Every Rate — arXiv:2610.40825 — arXiv (en), https://arxiv.org/abs/2610.40825 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_47c4cfbc478b (Metraipolis archive dc_47c4cfbc478b, sha256 c1e85cdf8308a67ed60341e3cff95815cf7e652d7b4ac1ed8944e15644825c35)
BibTeX
@misc{dc47c4cfbc478b,
title = {On the NP-Hardness of Rank-Metric Minimum Distance and Syndrome Decoding, at Every Rate — arXiv:2610.40825},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.40825},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_47c4cfbc478b; sha256 c1e85cdf8308a67ed60341e3cff95815cf7e652d7b4ac1ed8944e15644825c35},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40825. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In this work, we investigate the hardness of computing minimum distance, as well as the hardness of syndrome decoding, for rank-metric codes. It is known (Gaborit and Zémor, IEEE TIT 2016) that for $\mathbb{F}_{q^m}$-linear rank-metric codes of length $N$, minimum distance when $m=O(N)$ and syndrome decoding when $m=O(N^2)$ are NP-hard under randomized reductions. We obtain a derandomization of these results and a bit more. We show that for any fixed small $\varepsilon>0$, for $\mathbb{F}_{q^m}$-linear rank-metric codes of length $N$ with $m=O(N^{1+\varepsilon})$, the problems of minimum distance, nearest codeword, and syndrome decoding are NP-hard under deterministic reductions. Further, we can prescribe the rate; that is, if we restrict to codes having any fixed rational rate $R\in(0,1)$, then the NP-hardness for all three problems persists. Our main technical contribution is simple, and possibly of independent interest. The reduction of Gaborit and Zémor (IEEE TIT 2016) relies on a distance-preserving embedding of a Hamming-metric code into a rank-metric code, obtained by multiplying its coordinates by a uniformly random vector. We show that we can choose an explicit vector from a slightly larger extension field.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.40825 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T08:08:23.797Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).