Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-109 | 30th June 2024 09:35

On the Cook-Mertz Tree Evaluation procedure

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 30th June 2024 09:35
Downloads: 182
Keywords: 


Abstract:

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.

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.



Changes to previous version:

Most importantly, as pointed out by Ben Chen, the result stated in Theorem 2 was also proved by Cook and Mertz.

In addition, we corrected a few typos.


Paper:

TR24-109 | 29th June 2024 16:09

On the Cook-Mertz Tree Evaluation procedure





TR24-109
Authors: Oded Goldreich
Publication: 29th June 2024 16:09
Downloads: 228
Keywords: 


Abstract:

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.

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.



ISSN 1433-8092 | Imprint