Tree Evaluation is in Space O(log n * log log n)

by James Cook and Ian Mertz

Oded's comments

It seems that this result requires no introduction. Still, let me risk and say a few words.

As stated in the abstract, this work casts in much deeper doubt a natural candidate for separating P from L. Specifically, it improves the space bound for this candidate from slightly below quadratic-log space to almost-log space.

What is a bit confusing is that it is raising the bet on the KRW conjeture (regarding composition in the context of circuit depth). On the one hand, the new result asserts that the KRW Conjecture implies not only that NC1 cannot emulate P (which is well-knwon) but rather that it cannot even emulate L. On the other hand, the new result may be viewed as contradicting a natural analogous of the KRW conjecture for space.

An apology (18-Nov-23): By mistake, the initial posting startng with the sentence ``It seems that this result deserves no introduction.'' I have been telling a story about the confusion between requires and deserves for decades, and I guess this is the cause of my own mental typo.

The original abstract

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 solved in space $O(\log^2 n/ \log \log n)$. Thus its status as a candidate hard problem for $L$ remains a mystery.

Our main result is to improve the space complexity of TreeEval to $O(\log n \cdot \log \log n)$, thus greatly strengthening the case that Tree Evaluation is in fact in $L$.

We show two consequences of these results. First, we show that the KRW conjecture (Karchmer, Raz, and Wigderson 1995) implies $L \neq NC^1$; this itself would have many implications, such as branching programs not being efficiently simulable by formulas. Our second consequence is to increase our understanding of amortized branching programs, also known as catalytic branching programs; we show that every function $f$ on $n$ bits can be computed by such a program of length poly$(n)$ and width $2^{O(n)}$.

See ECCC TR23-174.

Back to list of Oded's choices.