# 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. – David Mar 15 '11 at 15:52