{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidsj6po3o7mx5yds6uwuozmzleceder6b2tl64tirtwjf7z7gfnge",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mistwtpgzbn2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.02606v1",
  "publishedAt": "2026-04-06T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Vahid R. Asadi",
    "Richard Cleve"
  ],
  "textContent": "**Authors:** Vahid R. Asadi, Richard Cleve\n\nThe Tree Evaluation Problem ($\\mathsf{TreeEval}$) is a computational problem originally proposed as a candidate to prove a separation between complexity classes $\\mathsf{P}$ and $\\mathsf{L}$. Recently, this problem has gained significant attention after Cook and Mertz (STOC 2024) showed that $\\mathsf{TreeEval}$ can be solved using $O(\\log n\\log\\log n)$ bits of space. Their algorithm, despite getting very close to showing $\\mathsf{TreeEval} \\in \\mathsf{L}$, falls short, and in particular, it does not run in polynomial time. In this work, we present the first polynomial-time, almost logarithmic-space algorithm for $\\mathsf{TreeEval}$. For any $\\varepsilon>0$, our algorithm solves $\\mathsf{TreeEval}$ in time $\\mathrm{poly}(n)$ while using $O(\\log^{1 +\\varepsilon}n)$ space. Furthermore, our algorithm has the additional property that it requires only $O(\\log n)$ bits of free space, and the rest can be catalytic space. Our approach is to trade off some (catalytic) space usage for a reduction in time complexity.",
  "title": "Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling"
}