Computational Hardness of the Permuted Kernel and Subcode Equivalence Problems

ePrint Report: Computational Hardness of the Permuted Kernel and Subcode Equivalence Problems

Paolo Santini, Marco Baldi, Franco Chiaraluce

The Permuted Kernel Problem (PKP) asks to find a permutation which makes an input matrix an element of the kernel of some given vector space. The literature exhibits several works studying its hardness in the case of the input matrix being mono-dimensional (i.e., a vector), while the multi-dimensional case has received much less attention and, de facto, only the case of a …

computational eprint report kernel problems