TCS Journal 2026 Journal Article
Pseudorandom generators for sliding-window algorithms
- Augusto Modanese
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 G base with seed length d base 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 d base + O ( log ( n / t ) log ( 1 / ε base ) ) random bits, whereas the second has a seed length of O ( ( d base + log log ( n / t ) + log ( 1 / ε base ) ) log ( d base + log ( 1 / ε base ) ) ). 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. , log w = ( log ( n / ε ) ) 1. 01 ). 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) T ( n ) = Ω ( log n ) 1. 01, 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 O ˜ ( T ) + O ( log n ) space instead (where the O ˜ notation hides only polylog ( T ) factors).