@online{Fischer2605.31417,
TITLE = {An Optimal Algorithm for Binary Closest String},
AUTHOR = {Fischer, Nick and Habib, Mursalin},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2605.31417},
EPRINT = {2605.31417},
EPRINTTYPE = {arXiv},
YEAR = {2026},
ABSTRACT = {We revisit the Binary Closest String problem, which asks, given a set of binary strings $X \subseteq \{0, 1\}^n$, to compute a string minimizing the maximum Hamming distance to $X$. A long line of work has focused on parameterized algorithms with respect to the optimal distance $d$, yielding a sequence of improvements from $O^*(d^d)$ through $O^*(16^d)$, $O^*(9.513^d)$, $O^*(8^d)$, $O^*(6.731^d)$ to the current best-known running time of $O^*(5^d)$ [Chen, Ma, Wang; Algorithmica '16]. We present a faster randomized algorithm running in time $O^*(4^d)$. Our result matches a recent fine-grained lower bound [Abboud, Fischer, Goldenberg, Karthik C.S., Safier; ESA '23], and is therefore conditionally optimal. As an extra benefit, our algorithm is remarkably simple.},
}