Catalytic approaches to the tree evaluation problem

The study of branching programs for the Tree Evaluation Problem (TreeEval), introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in [𝑘] at each leaf of a complete binary tree and an explicit function in [𝑘] 2 → [𝑘] for recursively computing the value of each internal node from its children, the problem is to compute the value at the root node. (While the original problem allows an arbitrary-degree tree, we focus on binary trees.) The problem is parameterized by the alphabet size 𝑘 and the height ℎ of the tree.

A branching program implementing the straightforward recursive algorithm uses Θ((𝑘 + 1) ℎ ) states, organized into 2 ℎ -1 layers of width up to 𝑘 ℎ . Until now no better deterministic algorithm was known.

We present a series of three new algorithms solving TreeEval. They are inspired by the work of Buhrman et al. on catalytic space (STOC 2012), applied outside the catalytic-space setting. First we give a novel branching program with 2 4ℎ poly(𝑘) layers of width 2 3𝑘 , which beats the straightforward algorithm when ℎ = 𝜔 (𝑘/log 𝑘). Next we give a branching program with 𝑘 2ℎ poly(𝑘) layers of width 𝑘 3 . This has total size comparable to the straightforward algorithm, but is implemented using the catalytic framework. Finally we interpolate between the two algorithms to give a branching program with (𝑂 ( 𝑘 ℎ )) 2ℎ poly(𝑘) layers of width (𝑂 ( 𝑘 ℎ )) 𝜖ℎ for any constant 𝜖 > 0, which beats the straightforward algorithm for all ℎ ≥ 𝑘 1/2+poly 𝜖 . These are the first deterministic branching programs to beat the straightforward algorithm, but more importantly this is the first non-trivial approach to proving deterministic upper bounds for TreeEval.

We also contribute new machinery to the catalytic computing program, which may be of independent interest to some readers.

• Theory of computation → Computational complexity and cryptography; Design and analysis of algorithms.