Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TREE EVALUATION PROBLEM:
Reports tagged with tree evaluation problem:
TR20-056 | 17th April 2020
James Cook, Ian Mertz

The study of branching programs for the Tree Evaluation Problem, introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in $[k]$ at each leaf of a complete binary tree and an explicit function in $[k]^2 \to ... more >>> TR21-054 | 14th April 2021 James Cook, Ian Mertz #### Encodings and the Tree Evaluation Problem We show that the Tree Evaluation Problem with alphabet size$k$and height$h$can be solved by branching programs of size$k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception. more >>> TR23-174 | 15th November 2023 James Cook, Ian Mertz #### Tree Evaluation is in Space O(log n ยท log log n) The Tree Evaluation Problem ($TreeEval$) (Cook et al. 2009) is a central candidate for separating polynomial time ($P$) from logarithmic space ($L$) via composition. While space lower bounds of$\Omega(\log^2 n)$are known for multiple restricted models, it was recently shown by Cook and Mertz (2020) that TreeEval can be ... more >>> TR24-109 | 29th June 2024 Oded Goldreich #### On the Cook-Mertz Tree Evaluation procedure Revisions: 1 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, ... more >>> TR24-124 | 26th July 2024 Oded Goldreich #### 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 ... more >>>

ISSN 1433-8092 | Imprint