A search-to-decision reduction for the linear code equivalence problem

Jean-François Biasse, Giacomo Micheli, Benjamin Prada +1

We present a polynomial-time reduction from the search variant of the linear code equivalence problem (i.e. the search for a linear isometry between the inputs) to its decisional v…