Search Results

Two linear error-correcting codes 𝒞₁, 𝒞₂ ⊆ F_qⁿ are called linearly equivalent if there is a linear isometry mapping 𝒞₁ to 𝒞₂. In this work, we generalize the notion of linear equivalence and study the minimum distortion 𝒟(𝒞₁, 𝒞₂) of a linear mapping between codes 𝒞₁, 𝒞₂ ⊆ F_qⁿ, which quantifies how similar 𝒞₁ and 𝒞₂ are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes 𝒞₁ and 𝒞₂. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where 𝒟(𝒞₁, C₂) = 1 and which is well-studied because of its role in cryptography. We prove that (decisional) CDP is NP-hard to approximate to within any constant factor, and that it is in Σ₂^P. We also give a single-exponential-time k²-approximation algorithm for CDP, where k is the dimension of the input codes. Furthermore, we give a single-exponential-time ((2k + 1)/3)²-approximation algorithm for a natural special case of CDP, and we show that our analysis is tight in this case. We use techniques from analogous work on the Lattice Distortion Problem (LDP) by Bennett, Dadush, and Stephens-Davidowitz (ESA, 2016). We also introduce or study a number of additional concepts that might be of independent interest. These include an adaptation of the celebrated reduction of Goldreich, Micciancio, Safra, and Seifert (IPL, 1999) from the Shortest Vector Problem (SVP) to the Closest Vector Problem (CVP) on lattices to the analogous problems on codes; successive minima bases for codes; and the matrix 0 → 0 "norm" on subspaces.