In this paper we study the hardness of the syndrome decoding problem over finite rings endowed with the Lee metric. We first prove that the decisional version of the problem is NP-complete, by a reduction from the 3-dimensional matching problem. Then, we study the complexity of solving the problem, by translating the best known solvers in the Hamming metric over finite fields to the Lee metric over finite rings, as well as proposing some novel solutions. For the analyzed algorithms, we assess the computational complexity in the asymptotic regime and compare it to the corresponding algorithms in the Hamming metric.
On the hardness of the Lee syndrome decoding problem / Weger, Violetta; Khathuria, Karan; Horlemann, Anna-Lena; Battaglioni, Massimo; Santini, Paolo; Persichetti, Edoardo. - In: ADVANCES IN MATHEMATICS OF COMMUNICATIONS. - ISSN 1930-5346. - ELETTRONICO. - 0:0(2022), p. 0. [10.3934/amc.2022029]
On the hardness of the Lee syndrome decoding problem
Battaglioni, Massimo;Santini, Paolo;Persichetti, Edoardo
2022-01-01
Abstract
In this paper we study the hardness of the syndrome decoding problem over finite rings endowed with the Lee metric. We first prove that the decisional version of the problem is NP-complete, by a reduction from the 3-dimensional matching problem. Then, we study the complexity of solving the problem, by translating the best known solvers in the Hamming metric over finite fields to the Lee metric over finite rings, as well as proposing some novel solutions. For the analyzed algorithms, we assess the computational complexity in the asymptotic regime and compare it to the corresponding algorithms in the Hamming metric.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
