4
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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

$\endgroup$
1
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – David
    Mar 15 '11 at 15:52
  • $\begingroup$ The LLL algorithm often gives answers that are much better than the theoretical guarantee. $\endgroup$
    – Peter Shor
    Mar 15 '11 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.