Welcome to the resource topic for 2024/782
Title:
Relating Code Equivalence to Other Isomorphism Problems
Authors: Huck Bennett, Kaung Myat Htay Win
Abstract:We study the complexity of the Code Equivalence Problem on linear error-correcting codes by relating its variants to isomorphism problems on other discrete structures—graphs, lattices, and matroids. Our main results are a fine-grained reduction from the Graph Isomorphism Problem to the Linear Code Equivalence Problem over any field \mathbb{F}, and a reduction from the Linear Code Equivalence Problem over any field \mathbb{F}_p of prime, polynomially bounded order p to the Lattice Isomorphism Problem. Both of these reductions are simple and natural. We also give reductions between variants of the Code Equivalence Problem, and study the relationship between isomorphism problems on codes and linear matroids.
ePrint: https://eprint.iacr.org/2024/782
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .