2026/07/28 by Huck Bennett, Matthew Fox, Bryant Morrell
Computer Science · Mathematics · #cs.CC #cs.DS #cs.IT #math.IT #math.MG
APPROX 2026
arxiv created 2026/07/28 · arxiv updated 2026/07/30
Two linear error-correcting codes \calC1, \calC2 ⊆ \mathbbFqn are called linearly equivalent if there is a linear isometry mapping \calC1 to \calC2. In this work, we generalize the notion of linear equivalence and study the minimum distortion \calD(\calC1, \calC2) of a linear mapping between codes \calC1, \calC2 ⊆ \mathbbFqn, which quantifies how similar \calC1 and \calC2 are. We introduce and study the Code Distortion Problem (CDP), which asks to find a minimum distortion mapping between two input codes \calC1 and \calC2. CDP generalizes the Linear Code Equivalence Problem (LCE), which is essentially the special case of CDP where \calD(\calC1, C2) = 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 Σ2P. We also give a single-exponential-time k2-approximation algorithm for CDP, where k is the dimension of the input codes. Furthermore, we give a single-exponential-time ((2k + 1)/(3))2-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.