A sliding-window algorithm of window size t is an algorithm whose current operation depends solely on the last t symbols read. We construct pseudorandom generators (PRGs) for low-space randomized sliding-window algorithms that have access to a binary randomness source. More specifically, we lift these algorithms to the non-uniform setting of branching programs and study them as a subclass thereof that we call sliding-window branching programs (SWBPs), accordingly. For general SWBPs, given a base PRG Gbase with seed length dbase that εbase-fools width-w, length-t (general) branching programs, we give two PRG constructions for fooling any same-width SWBP of length n and window size t (where we assume w ≥ n). The first uses an additional random bits, whereas the second has a seed length of . Both PRGs incur only a (n/2t)O(1) multiplicative loss in the error parameter. We also give a hitting set generator (HSG) that achieves a slightly better seed length for regimes where log w is very close to log (n/ε) (e.g., ). As an application, we reveal a connection between the sliding-window model and space-bounded models of distributed computing. Concretely, we show how limited space is sufficient in order to deterministically decide a language accepted by a randomizedconstant-space distributed model. More specifically, our results target the model of PACAs, which are probabilistic cellular automata that accept if and only if all cells are simultaneously accepting. For (sublinear) , we prove that every language accepted by a T-time one-sided error PACA can be decided using only O(T) space. Meanwhile, forgoing the previous requirement on T, we show the same holds for T-time two-sided error PACA if we use space instead (where the notation hides only factors).
2026-04
2026-05-06