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.

**Added after discussion with Amnon Ta-Shma (12-June-24):**
Rather than discussing the catalytic space model,
I prefer to use the model of global-tape oracle machines
presented in Definition 5.8 of
my computational complexity book.
(The catalytic model is a special case.)
The crux of the current result is that
any Boolean function over $\{0,1\}^\ell$ can be computed
by this model using global space $O(\ell\log\ell)$
and local space $O(\log\ell)$.
Furthermore, this holds also if the input bits are obtained by oracle calls.
Hence, using Lemma 5.10,
TreeEval for depth $d$ and $k$-bit long inputs at the leaves
can be computed in (the standrad model in) space $O((d+k)\log k)$.
As for the crux itself, it is proved by taking low-degree extensions
of the original functions and manipulating them within a field
that has more that $\ell$ elements.

**Added on 26-June-24:**
my overview and digest.

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