Abstract
We study the fundamental problem of finding the best string to represent a given set, in the form of the Closest String problem: Given a set X ⊆ Σ^d of n strings, find the string x^* minimizing the radius of the smallest Hamming ball around x^* that encloses all the strings in X. In this paper, we investigate whether the Closest String problem admits algorithms that are faster than the trivial exhaustive search algorithm. We obtain the following results for the two natural versions of the problem:
 In the continuous Closest String problem, the goal is to find the solution string x^* anywhere in Σ^d. For binary strings, the exhaustive search algorithm runs in time O(2^d poly(nd)) and we prove that it cannot be improved to time O(2^{(1ε) d} poly(nd)), for any ε > 0, unless the Strong Exponential Time Hypothesis fails.
 In the discrete Closest String problem, x^* is required to be in the input set X. While this problem is clearly in polynomial time, its finegrained complexity has been pinpointed to be quadratic time n^{2 ± o(1)} whenever the dimension is ω(log n) < d < n^o(1). We complement this known hardness result with new algorithms, proving essentially that whenever d falls out of this hard range, the discrete Closest String problem can be solved faster than exhaustive search. In the smalld regime, our algorithm is based on a novel application of the inclusionexclusion principle. Interestingly, all of our results apply (and some are even stronger) to the natural dual of the Closest String problem, called the Remotest String problem, where the task is to find a string maximizing the Hamming distance to all the strings in X.
BibTeX  Entry
@InProceedings{abboud_et_al:LIPIcs.ESA.2023.3,
author = {Abboud, Amir and Fischer, Nick and Goldenberg, Elazar and Karthik C. S. and Safier, Ron},
title = {{Can You Solve Closest String Faster Than Exhaustive Search?}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {3:13:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18656},
URN = {urn:nbn:de:0030drops186566},
doi = {10.4230/LIPIcs.ESA.2023.3},
annote = {Keywords: Closest string, finegrained complexity, SETH, inclusionexclusion}
}
Keywords: 

Closest string, finegrained complexity, SETH, inclusionexclusion 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 