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

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).

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.
• Interesting idea, although the LLL algorithm only seems to guarantee that the basis b_1, b_2,....,b_(m-n+2) () satisfies: $|b_i| \le \exp(ci)$ ... so for large i the vectors b_i may still be very large. But maybe for the specific class of A I have in mind they turn out to be short. Maybe I'll run some simulations to find out. () Not sure if that's really the dimension of the lattice. Mar 15 '11 at 15:52