This paper is being withdrawn due to an error in the calculation of the polynomial degree for each subtree.

The authors are withdrawing this paper due to an error in the calculation of the polynomial degree for each subtree. As a result, the proposed algorithm does not achieve polynomial time complexity as originally claimed. The authors intend to revise the manuscript upon further investigation.

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.