ECCC-Report TR24-109https://eccc.weizmann.ac.il/report/2024/109Comments and Revisions published for TR24-109en-usSun, 30 Jun 2024 09:35:54 +0300
Revision 1
| On the Cook-Mertz Tree Evaluation procedure |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2024/109#revision1The 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.
We provide an exposition and a digest of the recent result of Cook and Mertz ({\em ECCC}, TR23-174), which asserts that Tree Evaluation problem can be solved in space $O((h+\ell)\cdot \log\ell)$.
In particular, we point out that the algebraic manipulation (using roots of unity) performed in the original work is merely a special case of univariate polynomial interpolation.
Using this observation we provide a more transparent exposition of their main result as well as its low order quantitative improvement (i.e., space complexity $O(\ell+h\cdot\log\ell)$).
Our exposition refers to the ``global storage'' model rather than to the ``catalytic storage'' model used by Cook and Mertz, which can be viewed as a special case.
We believe that the global storage model is more flexible and intuitive, but our exposition can be easily adapted to the catalytic storage model. Sun, 30 Jun 2024 09:35:54 +0300https://eccc.weizmann.ac.il/report/2024/109#revision1
Paper TR24-109
| On the Cook-Mertz Tree Evaluation procedure |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2024/109The 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.
We provide an exposition and a digest of the recent result of Cook and Mertz ({\em ECCC}, TR23-174), which asserts that Tree Evaluation problem can be solved in space $O((h+\ell)\cdot \log\ell)$.
In particular, we point out that the algebraic manipulation (using roots of unity) performed in the original work is merely a special case of univariate polynomial interpolation.
Using this observation we provide a more transparent exposition of the result as well as a low order quantitative improvement (i.e., we improve the space complexity from $O((\ell+h)\cdot\log\ell)$ to $O(\ell+h\cdot\log\ell)$).
Our exposition refers to the ``global storage'' model rather than to the ``catalytic storage'' model used by Cook and Mertz, which can be viewed as a special case.
We believe that the global storage model is more flexible and intuitive, but our exposition can be easily adapted to the catalytic storage model. Sat, 29 Jun 2024 16:09:53 +0300https://eccc.weizmann.ac.il/report/2024/109