## 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.