{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreida5x7qt35hse42qn2vz4jugjkuqc4ampetke4r35anwm6u5uvxga",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mifxlinta6v2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.29702v1",
  "publishedAt": "2026-04-01T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Xiao Mao",
    "Aviad Rubinstein"
  ],
  "textContent": "**Authors:** Xiao Mao, Aviad Rubinstein\n\nWe present novel randomized approximation schemes for the Edit Distance (ED) problem and the Longest Common Subsequence (LCS) problem that, for any constant $ε>0$, compute a $(1+ε)$-approximation for ED and a $(1-ε)$-approximation for LCS in time $n^2 / 2^{\\log^{Ω(1)}(n)}$ for two strings of total length at most $n$. This running time improves upon the classical quadratic-time dynamic programming algorithms by a quasi-polynomial factor. Our results yield significant insights into fine-grained complexity: Firstly, for ED, prior work indicates that any exact algorithm cannot be improved beyond a few logarithmic factors without refuting established complexity assumptions [Abboud, Hansen, Vassilevska Williams, Williams, 2016]; our quasi-polynomial speed-up shows a separation the complexity of approximate ED from that of exact ED, even for approximation factor arbitrarily close to $1$. Secondly, for LCS, obtaining similar approximation-time tradeoffs via deterministic algorithms would imply breakthrough circuit lower bounds [Chen, Goldwasser, Lyu, Rothblum, Rubinstein, 2019]; our randomized algorithm demonstrates derandomization hardness for LCS approximation.",
  "title": "Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time"
}