On explicit reductions between two purely algebraic problems: MQ and MLD
published by Alessio Meneghetti
in 2021
in Informatics Engineering
and research's language is
English
Download
Abstract in English
The Maximum Likelihood Decoding Problem (MLD) and the Multivariate Quadratic System Problem (MQ) are known to be NP-hard. In this paper we present a polynomial-time reduction from any instance of MLD to an instance of MQ, and viceversa.