An Optimal Algorithm for Binary Closest String

Authors: Nick Fischer, Mursalin Habib

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.