# How many strings for CLOSEST STRING lower bound to apply

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?

• 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$". Commented Dec 16, 2020 at 3:19
• If you follow the proof in the paper, you will see what value of $t$ their reduction gives. Commented Dec 16, 2020 at 8:51
• 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. Commented Dec 16, 2020 at 8:53