Recent searches
Search options
♬ 
@peterrenshaw@ioc.exchange“Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)”
‘The #TreeEvaluation #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 Ω(log2 n) are known for multiple restricted models, it was recently shown by #Cook and #Mertz (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.
Our main result is to improve the space complexity of #TreeEval 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 #KRWconjecture (#Karchmer, #Raz, and #Wigderson 1995) implies L ⊈NC1; this itself would have many implications, such as branching programs not being efficiently simulable by formulas’
You Need Much Less #Memory than #Time
“Just as I was complaining that we haven't seen many surprising breakthroughs in complexity recently, we get an earthquake of a result to start the year, showing that all #algorithms can be simulated using considerable less memory than the time of the original algorithm. You can #reuse space (#memory) but you can't reuse time, and this new result from #RyanWilliams in an upcoming #STOC paper provides the first stark difference”
<https://blog.computationalcomplexity.org/2025/02/you-need-much-less-memory-than-time.html?m=1>
“Astonishing #discovery by computer #scientist: how to squeeze space into time”
#KelseyHoustonEdwards PhD / #ChalkTalk / #computation / <https://youtube.com/watch?v=8JuWdXrCmWg>