Can we use ``hardness vs randomness'' techniques to design low-space algorithms? This text surveys a sequence of recent works showing ways to do that.
These works designed algorithms for certified derandomization and for catalytic computation (which work unconditionally), derandomization and isolation algorithms from remarkably mild assumptions, and ``win-win'' pairs ... more >>>

The Tree Evaluation Problem (TreeEval) is a computational problem originally proposed as a candidate to prove a separation between complexity classes P and L. Recently, this problem has gained significant attention after Cook and Mertz (STOC 2024) showed that TreeEval can be solved using $O(\log n\log\log n)$ bits of space. ... more >>>

Since the breakthrough superpolynomial multilinear formula lower bounds of Raz (Theory of Computing 2006), proving such lower bounds against multilinear algebraic branching programs (mABPs) has been a longstanding open problem in algebraic complexity theory. All known multilinear lower bounds rely on the min-partition rank method, and the best bounds against ... more >>>