1
$\begingroup$

If I have a list of $2^{2k}$ bitstrings of length $2k+1$ and each have a pairwise Hamming distance $\leq 2k$ is it possible to find a bitstring (either one of the ones on the list or another one) such that the Hamming distance (or some other metric) between it and every other string is $\leq k$. If it is possible is there an efficient algorithm for doing so?

I have a feeling that there may not be a solution with regards to my specific question since I'm thinking that there are $2^{2^{2k}}$ different sets of strings with pairwise Hamming distance $\leq 2k$ (just think of chosing a string or the string with every bit flipped) and only $2^{2k+1}$ possible "centers". However, I'm not sure. I'm hoping that this may be possible with some other metric.

$\endgroup$
1
$\begingroup$

The counting argument you're grasping towards works to show that there is not always a possible center.

When you have a set $2^{2k}$ strings of length $2k+1$, that's exactly half of all strings with length $2k+1$. Also it is not possible to have both a string and its negation in the set, because they would have Hamming distance $2k+1$. This means that for every string, either it or its negation has to be in the set, or the set wouldn't be large enough.

And this means that for any particular choice of "center" you can reconstruct exactly what the original list must have been -- namely, every string with a Hamming distance of $> k$ from the center has to be excluded, which means that its negation (which has a distance of $\le k$ from the center) must be included. This fixes the included-or-excluded status of every possible string.

So there's only one list that works for each "center", which, as you notice are much fewer than the number of possible lists (unless $k=0$, which is kind of a degenerate case).


If you have a list (or rather, an oracle that determines membership in the list) and know that is has a possible center, is it easy to determine what that center is with a small number of queries to the oracle? Yes:

First find two strings with Hamming distance $1$ where one of them is in the set and the other isn't. (For example, just try all strings of the form $1^n0^{2k+1-n}$ until the answer you get changes). This will immediately tell you what the right bit at the position where the two strings differ is. For each other position, take the string you know is just outside the set and see if it goes inside if you flip that bit. If it does, the flipped bit was right, otherwise the original bit was.

In this way you can determine the center in at most $3k+1$ queries to the oracle (modulo possible fencepost errors, but it should be thereabout).

$\endgroup$
  • $\begingroup$ Thank you. Do you know if there would be more sets covered by other metrics such as the Levenshtein distance? $\endgroup$ – Ari Nov 2 '15 at 21:26

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.