Solving Tree Evaluation in \(o(\log n \cdot \log \log n)\) Space
摘要
The input to the Tree Evaluation problem is a binary tree of height h in which each internal vertex is associated with a function mapping pairs of \(\ell \) -bit strings to \(\ell \) -bit strings, and each leaf is assigned an \(\ell \) -bit string. The desired output is the value of the root, where the value of each internal node is defined by applying the corresponding function to the value of its children. A recent result of Cook and Mertz (ECCC, TR23-174) asserts that the Tree Evaluation problem can be solved in space \(O(\ell +h\cdot \log \ell )\) , where the input length is \(\exp (\varTheta (h+\ell ))\) . Building on our recent exposition of their result (ECCC, TR24-109), we obtain an \(o((h+\ell )\cdot \log (h+\ell ))\) space bound. Specifically, for the case of \(h\ge \ell \) , we shave off an \(\varTheta (\log \log (h+\ell ))\) factor. The improvement is obtained by improving the procedure of Cook and Mertz for a generalized tree evaluation problem that refers to d-ary trees. We then reduce the binary case to the d-ary case while cutting the height of the tree by a factor of \(\log _2d\) .