Efficacy of the Metropolis Algorithm for the Minimum Weight Codeword Problem using Codeword and Generator Search Spaces

This paper studies the efficacy of the Metropolis algorithm for the minimum weight codeword problem. The input is a linear code C given by its generator matrix and our task is to compute a non-zero codeword in the code C of least weight. In particular, we study the Metropolis algorithm on two possible search spaces for the problem, the codeword space and the generator space. The former is the space of all codewords of the input code and is the most natural one to use and hence has been used in previous work on this problem. The latter is the space of all generator matrices of the input code and is studied for the first time in this work. In this paper, we show that for an appropriately chosen temperature parameter the Metropolis algorithm mixes rapidly when either of the search spaces mentioned above are used. Experimentally, we demonstrate that the Metropolis algorithm performs favourably when compared to previous attempts. When using the generator space, the Metropolis algorithm is able to outperform the previous algorithms in most of the cases. We have also provided both theoretical and experimental justification to show why the generator space is a worthwhile search space to use for this problem.