{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicznqwkhnzad7lfwn2sd6i3cidl3yykefml3fyeo3l5537353roea",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mn7een3ohaa2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.31417v1",
  "publishedAt": "2026-06-01T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Nick Fischer",
    "Mursalin Habib"
  ],
  "textContent": "**Authors:** Nick Fischer, Mursalin Habib\n\nWe 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.",
  "title": "An Optimal Algorithm for Binary Closest String"
}