Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$

Question

Let $W$ be a linear subspace of the vector space $V = (\mathbb{Z}/2\mathbb{Z})^n$. Let $k = \dim(W)$. For $v \in V$, define the distance from $v$ to $W$ to be $d(v,W):=\min_{w\in W} d(v,w)$ where $d(v,w)$ is the Hamming distance.

Given such a subspace $W$ (more precisely, receiving a basis of $k$ vectors as input), how can I find a vector $v \in V$ such that $d(v,W)$ is as large as possible?

The cases I'm interested in have $n$ in the thousands, but $k$ being quite small, usually less than 20. I have been able to solve some smaller instances of this problem ($n$ being a few hundred, $k$ being at most 6 or so) using the SAT/SMT solver Z3 by creating $n$ Boolean variables and explicitly writing out $d(v,w)\geq r$ for all $2^k$ elements of $W$ as clauses. The inequality is encoded using a pseudo-boolean constraint (pb-ge in Z3) stating that at least $r$ of the $n$ literals must be true in each clause. I then use a binary search to find the maximum value of $r$ where the formula is satisfiable.

Example: Let $n = 100$ and $W$ be the subspace spanned by the following three elements (I'll compress the notation a bit and write a vector like $(a,b,c)$ as $abc$):

1011000001001001000110000000110010000010111011100101010000010101001000000011001000011001110010000000 0100101000001010101011010000000001001000101111100010000010000001011101000001100100010001000100010010 1110010000000000110001011000110001000010011000001000101001001100100110100001010000011000001000110100

Then a solution to the problem is given by the following vector $v$:

1101101110110101010011101111011100111101110000010110110111111011101110011101100011101110110001101011

which has Hamming distance at least 64 from every linear combination of the three vectors above. Distance 65 from every linear combination is not possible.

Some additional questions:

• Does this problem have a name?
• Is there a faster (in practise, not necessarily in theory) algorithm than what I am currently doing?
• If so, is there an implementation that I can use?

Answer 1

Your problem is very likely NP-hard. If you don't add the restriction that $W$ is sub-space, but just receive a set of boolean vectors $W$, then it is NP-hard and known as a Covering Radius proven NP-hard by Frances and Litman. Of course it might be that $W$ being a sub-space somehow makes the problem easier, but I can't see a particular way for that to happen.

Answer 2

You may be interested in some linear algebra over finite field $\mathbb{F}_2$. Basically, vectors in the linear complement to $W$ should have the maximal Hamming distance. The trouble is that linear algebra over finite fields is not as straightforward as over $\mathbb{C}$. Nevertheless, linear algebra over $\mathbb{F}_2$ has been applied to Hamming codes.