We establish an equivalence between two algorithmic tasks: *derandomization*, the deterministic simulation of probabilistic algorithms; and *refutation*, the deterministic construction of inputs on which a given probabilistic algorithm fails to compute a certain hard function.

We prove that refuting low-space probabilistic streaming algorithms that try to compute functions $f\in\mathcal{FP}$ is equivalent to proving that $pr\mathcal{BPP}=pr\mathcal{P}$, even in cases where a lower bound for $f$ against this class (without a refuter) is already unconditionally known. We also demonstrate the generality of the connection between refutation and derandomization, by establishing connections between refuting classes of constant-depth circuits of sublinear size and derandomizing constant-depth circuits of polynomial size with threshold gates (i.e., $\mathcal{TC}^0$).

Our connection generalizes and strengthens recent work on the characterization of derandomization. In particular, using refuter terminology allows to directly compare several recent works to each other and to the current work, as well as to chart a path for further progress. Along the way, we also improve the targeted hitting-set generator of Chen and Tell (FOCS 2021), showing that its translation of hardness to pseudorandomness scales down to $\mathcal{TC}^0$.