{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicwi7p2lwvsur543dxmt2bz63wodjwl7vi4x7qkstaddoyu5bw6ne",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfnrvsw2a7n2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.21089v1",
  "publishedAt": "2026-02-25T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Petr Chmel",
    "Aditi Dudeja",
    "Michal Koucký",
    "Ian Mertz",
    "Ninad Rajgopal"
  ],
  "textContent": "**Authors:** Petr Chmel, Aditi Dudeja, Michal Koucký, Ian Mertz, Ninad Rajgopal\n\nWe develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only $\\mathcal{O}(\\log(n))$ workspace, and use sublinear catalytic space matching the best-known space bounds of non-catalytic algorithms running in polynomial time. First, we design a polynomial time algorithm for directed $s$-$t$ connectivity using $n \\big/ 2^{Θ(\\sqrt{\\log n})}$ catalytic space, which matches the state-of-the-art time-space bounds in the non-catalytic setting [Barnes et al., 1998], and improves the catalytic space usage of the best known algorithm [Cook and Pyne, 2026]. Furthermore, using only $\\mathcal{O}(\\log(n))$ random bits we get a randomized algorithm whose running time nearly matches the fastest time bounds known for space-unrestricted algorithms. Second, we design polynomial time algorithms for the problems of computing Edit Distance, Longest Common Subsequence, and the Discrete Fréchet Distance, again using $n \\big/ 2^{Θ(\\sqrt{\\log n})}$ catalytic space. This again matches non-catalytic time-space frontier for Edit Distance and Least Common Subsequence [Kiyomi et al., 2021].",
  "title": "Frontier Space-Time Algorithms Using Only Full Memory"
}