51 citations · 146 across the 39 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
Reductions Between Code Equivalence Problems
Mahdi Cheraghchi, Nikhil Shagrithaya, Alexandra Veliche
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 Li…
cs.CC2022
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all Norms
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami +1
We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any co…