{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigp6jirjibvs54nqlcvnbrjq25f2rvglahwcfbbzshh7nakluumdq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mis74256iry2"
  },
  "path": "/report/2026/044",
  "publishedAt": "2026-04-05T08:45:29.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "The Tree Evaluation Problem (TreeEval) is a computational problem originally proposed as a candidate to prove a separation between complexity classes P and L. Recently, this problem has gained significant attention after Cook and Mertz (STOC 2024) showed that TreeEval can be solved using $O(\\log n\\log\\log n)$ bits of space. Their algorithm, despite getting very close to showing TreeEval $\\in$ 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 TreeEval. For any $\\varepsilon>0$, our algorithm solves 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": "TR26-044 |  Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling | \n\n\tVahid Reza Asadi, \n\n\tRichard Cleve"
}