Table of Contents: :: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Cheraghchi, Mahdi, Shagrithaya, Nikhil, Veliche, Alexandra
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2502.07916
Tags:	Add Tag No Tags, Be the first to tag this record!

Table of Contents:

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) proved in a paper by Bennett and Win (2024), our second result implies a reduction from PCE to LIP.