Is code equivalence easy to decide?
From MaRDI portal
Publication:4371902
DOI10.1109/18.623157zbMath0884.94025MaRDI QIDQ4371902
Publication date: 13 April 1998
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/5c1624d163a4fb426f8dbf4929628031a1575c08
NP-complete; interactive proofs; code equivalence; graph isomorphism problem; equivalent linear codes
68Q25: Analysis of algorithms and problem complexity
94B05: Linear codes (general theory)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Algorithms for Group Isomorphism via Group Extensions and Cohomology, A NP-Complete Problem in Coding Theory with Application to Code Based Cryptography, Semantic security for the McEliece cryptosystem without random oracles, Hulls of cyclic and negacyclic codes over finite fields, On isomorphism testing of groups with normal Hall subgroups, Quantum algorithms for algebraic problems, A Provably Secure Signature and Signcryption Scheme Using the Hardness Assumptions in Coding Theory, Zero-Knowledge Interactive Proof Systems for New Lattice Problems, On a Gröbner bases structure associated to linear codes