Trading time, space, and alternations: General plasticity for algorithms from hardness of range...

Zeyong Li (University of Toronto) https://simons.berkeley.edu/talks/zeyong-li-university-toronto-2026-10-29 Derandomization In a recent breakthrough, Williams (STOC 2025) showed that any decision problem solvable in time $t$ by a multitape Turing machine can be solved in space $\tilde{O}(\sqrt{t})$ and time $2^{\tilde{O}(\sqrt{t})}$. The immediate question is whether this result is an anomaly, or an inherent feature of computation more generally. In this work we provide evidence that the resource trade-offs phenomenon first demonstrated by Williams is systematic, i.e. inherent to computation in general. Specifically, under a plausible complexity-theoretic hardness assumption, we show that $t$-time algorithms can be simulated in space $t^{\epsilon}$, for any constant $\epsilon＞0$, where the simulation is correct on average over a random input. We also show, under similar complexity-theoretic hardness assumptions, that $t$-time algorithms can be simulated in \emph{linear time} using sufficiently many alternations (i.e., $\forall/\exists$ quantifiers), where again the simulation is correct on average over a random input. Some hardness assumption is necessary to prove these conclusions (as they imply that $\mathsf{P}\ne\mathsf{PSPACE}$), and the specific hardness assumption that we rely on has been extensively studied in complexity theory in recent years: hardness of a computational problem called Range Avoidance. Specifically, we introduce a new ``low-space'' variant of Range Avoidance, and show (under mild derandomization assumptions) that average-case hardness of this problem for polynomial-time algorithms is in fact \emph{equivalent} to low-space simulation of $\mathsf{FP}$, and implies linear-time simulation with alternations. We then study the complexity of this new problem, showing conditional hardness results and algorithms. Joint work with Roei Tell.