Reductions Between Code Equivalence Problems

Reductions Between Code Equivalence Problems. Cheraghchi, M., Shagrithaya, N., & Veliche, A. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2025.
abstract bibtex

In this paper, we present two reductions between variants of the Code Equivalence problem. We give polynomial-time Karp reductions from Permutation Code Equivalence (PCE) to both Linear Code Equivalence (LCE) and Signed Permutation Code Equivalence (SPCE). Along with a Karp reduction from SPCE to the Lattice Isomorphism Problem LIP shown by Bennett and Win (2024), our second result implies a reduction from PCE to LIP.

@INPROCEEDINGS{ref:CSV25,
  author =	 {Mahdi Cheraghchi and Nikhil Shagrithaya and Alexandra Veliche},
  title =	 {Reductions Between Code Equivalence Problems},
  year =	 2025,
  booktitle =	 {Proceedings of the {IEEE International Symposium on
                  Information Theory (ISIT)}},
  abstract =	 {In this paper, we present two reductions between variants of the Code Equivalence problem. 
    We give polynomial-time Karp reductions from Permutation Code Equivalence (PCE) to both Linear Code Equivalence (LCE) and Signed Permutation Code Equivalence (SPCE). 
    Along with a Karp reduction from SPCE to the Lattice Isomorphism Problem LIP shown by Bennett and Win (2024), our second result implies a reduction from PCE to LIP.}
}

Downloads: 0

{"_id":"oCEXm2Cv5fEBmoAsQ","bibbaseid":"cheraghchi-shagrithaya-veliche-reductionsbetweencodeequivalenceproblems-2025","author_short":["Cheraghchi, M.","Shagrithaya, N.","Veliche, A."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["Nikhil"],"propositions":[],"lastnames":["Shagrithaya"],"suffixes":[]},{"firstnames":["Alexandra"],"propositions":[],"lastnames":["Veliche"],"suffixes":[]}],"title":"Reductions Between Code Equivalence Problems","year":"2025","booktitle":"Proceedings of the IEEE International Symposium on Information Theory (ISIT)","abstract":"In this paper, we present two reductions between variants of the Code Equivalence problem. We give polynomial-time Karp reductions from Permutation Code Equivalence (PCE) to both Linear Code Equivalence (LCE) and Signed Permutation Code Equivalence (SPCE). Along with a Karp reduction from SPCE to the Lattice Isomorphism Problem LIP shown by Bennett and Win (2024), our second result implies a reduction from PCE to LIP.","bibtex":"@INPROCEEDINGS{ref:CSV25,\n author =\t {Mahdi Cheraghchi and Nikhil Shagrithaya and Alexandra Veliche},\n title =\t {Reductions Between Code Equivalence Problems},\n year =\t 2025,\n booktitle =\t {Proceedings of the {IEEE International Symposium on\n Information Theory (ISIT)}},\n abstract =\t {In this paper, we present two reductions between variants of the Code Equivalence problem. \n We give polynomial-time Karp reductions from Permutation Code Equivalence (PCE) to both Linear Code Equivalence (LCE) and Signed Permutation Code Equivalence (SPCE). \n Along with a Karp reduction from SPCE to the Lattice Isomorphism Problem LIP shown by Bennett and Win (2024), our second result implies a reduction from PCE to LIP.}\n}\n\n","author_short":["Cheraghchi, M.","Shagrithaya, N.","Veliche, A."],"key":"ref:CSV25","id":"ref:CSV25","bibbaseid":"cheraghchi-shagrithaya-veliche-reductionsbetweencodeequivalenceproblems-2025","role":"author","urls":{},"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","dataSources":["YZqdBBx6FeYmvQE6D"],"keywords":[],"search_terms":["reductions","between","code","equivalence","problems","cheraghchi","shagrithaya","veliche"],"title":"Reductions Between Code Equivalence Problems","year":2025}