☮ ♥ ♬ 🧑‍💻<p>“Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)”</p><p>‘The <a href="https://ioc.exchange/tags/TreeEvaluation" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>TreeEvaluation</span></a> <a href="https://ioc.exchange/tags/Problem" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Problem</span></a> (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 Ω(log2 n) are known for multiple restricted models, it was recently shown by <a href="https://ioc.exchange/tags/Cook" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Cook</span></a> and <a href="https://ioc.exchange/tags/Mertz" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Mertz</span></a> (2020) that TreeEval can be solved in space O(log2 n/loglogn). Thus its status as a candidate hard problem for L remains a mystery. </p><p>Our main result is to improve the space complexity of <a href="https://ioc.exchange/tags/TreeEval" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>TreeEval</span></a> to O(logn · loglogn), 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 <a href="https://ioc.exchange/tags/KRWconjecture" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>KRWconjecture</span></a> (<a href="https://ioc.exchange/tags/Karchmer" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Karchmer</span></a>, <a href="https://ioc.exchange/tags/Raz" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Raz</span></a>, and <a href="https://ioc.exchange/tags/Wigderson" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Wigderson</span></a> 1995) implies L ⊈NC1; this itself would have many implications, such as branching programs not being efficiently simulable by formulas’</p><p>&lt;<a href="https://dl.acm.org/doi/10.1145/3618260.3649664" rel="nofollow noopener noreferrer" translate="no" target="_blank"><span class="invisible">https://</span><span class="ellipsis">dl.acm.org/doi/10.1145/3618260</span><span class="invisible">.3649664</span></a>&gt;</p>