On the NP-Hardness of Rank-Metric Minimum Distance and Syndrome Decoding, at Every Rate

Venkata Gandikota, Vatsal Jha, S. Venkitesh

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 T…