In the CLOSEST STRING problem, one is given (bit-)strings $s_1, \dots, s_t$, each of length $L$ and an integer $d$. The question to be answered is whether there exists a string $s$ that has hamming distance to each $s_i$ that is at most $d$.

In this paper, the authors show that (assuming ETH) the problem cannot be solved in time sub-exponential in $d$, but no requirements on $t$ seem to be placed. However, for $t = 2$, the problem seems to be easy.

Solution for t=2: Let $s_1$ and $s_2$ be the two input strings. Let $k$ be the hamming distance between $s_1$ and $s_2$. If $k/2 \leq d$, then output "yes", otherwise output "no".

Question: Which requirements on $t$ need to be placed for the lower bound in the paper to hold?

  • $\begingroup$ The problem is even easier for $t=1$ (or for $L=1$, or both, etc.) :-P "The problem cannot be solved in time sub-exponential in $d$" means "There is no way to solve any instance I might come up with of the problem, including an instance with large $t$, in time sub-exponential in $d$". $\endgroup$ Commented Dec 16, 2020 at 3:19
  • $\begingroup$ If you follow the proof in the paper, you will see what value of $t$ their reduction gives. $\endgroup$ Commented Dec 16, 2020 at 8:51
  • $\begingroup$ For any constant $t$, there are only $2^t$ types of indices, so the problem can be solved in $O(n^{2^t-1})$. This can be improved to $O(n^{2^{t-1}-1}+n)$ (recovering your result) by identifying a pattern with its complement. $\endgroup$ Commented Dec 16, 2020 at 8:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.