Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).

Question

Is there an efficient algorithm for finding the solution $x$ of

$b = Ax$

that minimizes the Hamming weight of $x$, where

• $A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo 2") of rank $n$,
• $n<m$, say $m=500$, $n=200$,
• $b$ is a $n$-length fixed vector over $\mathbb{F}_2$ ("a binary word"),
• $x$ is a $m$-length vector (also "a binary word").

Is there an algorithm that can efficiently find a solution that is sufficiently close to the minimum?

It would be enough if there was an efficient algorithm to find the element $z \in KerA$ that minimizes the Hamming distance between an arbitrary $x$ and $z$. (Let $x$ be a solution to the equation, then $x+z$ is the solution that minimizes the Hamming weight).

Answer 1

No (unless P=NP). This is the decoding problem for error-correcting codes and it is known to be NP-complete.

Answer 2

A reasonably good solution can perhaps sometimes be found with the LLL-algorithm: Consider the lattice of $\mathbb Z^{m+1}$ spanned by $(\xi,1),(k_i,0)$ and the vectors $(2,0,\dots,0,0),(0,2,0,\dots,0,0),\dots,(0,\dots,0,2,0)$, where $\xi$ is an arbitrary solution (lifted to the integers) modulo $2$ and where $k_1,k_2,\dots$ generate the kernel of $A$ modulo $2$ and search for a shortest vector of the form $(*,1)$ in this lattice. LLL computes a basis of this lattice consisting of reasonably short vectors.