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\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Solving Tree Evaluation in  \(o(\log n \cdot \log \log n)\) Space

  • Oded Goldreich

摘要

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\) .