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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .