# Find binary number with max hamming distance wrt given set of binary numbers

Suppose we have a set $$A$$ of binary numbers with the same length $$n$$. For example (with $$n=8$$):

$$A = \{ 10010011, 01011011, 00010010, 11110001\}$$

Now, I want to find the binary number $$z$$ (also with $$n$$ bits) such that the minimum hamming distance between $$z$$ and any of these numbers is maximized.

i.e. $$z = \arg \max \{ d(x,A) \mid x \in X\}$$

with

$$d(x,A) := \min \{ d(x,a) \mid a \in A\}$$

where $$X$$ is the set of all $$n$$-bit binary numbers, and $$d(x,a)$$ the hamming distance between $$x$$ and $$a$$.

Is there any efficient algorithm for this?

Obviously, if $$n$$ is small enough we can brute-force this, but I'm looking for something more efficient when $$n$$ is large. The size of $$A$$, on the other hand, can be assumed relatively small, so any algorithm polynomial in $$|A|$$ is fine. Also, it does not have to be an exact algorithm. Any algorithm that approximates the correct answer is welcome too.

• If all your numbers are 8 bits long, you can just check all possibilities. – Yuval Filmus Apr 2 '19 at 15:09
• @YuvalFilmus yes, but see my update. – Math-E-Mad-X Apr 2 '19 at 16:19
• Start weeding out bits with one value, only (xxxFxTxx, in your example). Set bits with a clear minority value to that (xxtFtTff): probably, the values with maximal minimum Hamming distance end with 101100. Construct a counter example. – greybeard Apr 3 '19 at 6:31
• @greybeard: A counterexample: 10001 (and 01001, and 00101, and 00011) all have minimum distance 2 from $\{01111, 11101, 11011, 10111, 00000\}$ despite making two non-minority-digit choices, while 00000 (from always choosing the minority digit) has minimum distance 0. – j_random_hacker Apr 3 '19 at 11:35

Here is the decision version of the problem, which we can the problem of farthest string.

Given $$m$$ length-$$n$$ binary strings $$s_1, s_2, \cdots, s_m$$ and a number $$k$$, determine whether there is a length-$$n$$ string $$s$$ such that $$d(s,s_i)\ge k$$ for all $$i$$.

There is the problem of closest string.

Given $$m$$ length-$$n$$ binary strings $$s_1, s_2, \cdots, s_m$$ and a number $$k$$, determine whether there is a length-$$n$$ string $$s$$ such that $$d(s,s_i)\le k$$ for all $$i$$.

### Farthest string is dual to closest string.

Let $$c$$ denote the map that changes a binary string to its 1's complement, i.e., switching 0 and 1 everywhere. For example, $$c(010010111)=101101000$$. Note that $$c\circ c = Id$$.

Given an instance of farthest string $$(m, n, s_1, s_2, \cdots, s_m, k, s)$$, we can construct an instance of closest string $$(m, n, c(s_1), c(s_2), \cdots, c(s_m), n-k, s)$$. Call this transformation of instances $$r$$.

For every string $$s$$ of length $$n$$, $$d(s,s_i)+d(s, c(s_i))=n.$$ Hence $$d(s,s_i)\ge k\text{ for all }i\ \Longleftrightarrow\ d(s,c(s_i))\le n-k\text{ for all }i.$$

So $$r$$ converts a yes-instance of farthest string to a yes-instance of closest string. Symmetrically, $$r$$ converts a yes-instance of closest string to a yes-instance of furthest string. Furthermore, $$r\circ r= Id$$.

So $$r$$ is a linear duality reduction between farthest string and closest string.