Space-efficient derandomization methods for complex branching models
SC Derandomization for Regular ROBPs and Models Beyond BPL
Computational Complexity
Summary
Derandomization is a way to make random processes in computing more predictable, using less memory space. This paper improves how computers can simulate random tests for certain structured programs called regular read-once branching programs, using very little memory. The authors also extend these methods to more powerful models that use randomness and memory in special ways, showing they can still be simplified without losing accuracy. These results help better understand the limits of efficient computation with randomness.
What this means in practice
- •For complexity theorists: Use new derandomization techniques to analyze and simplify space-bounded randomized computations beyond standard models.
- •For algorithm designers: Design algorithms for space-limited devices that approximate probabilistic computations with guaranteed low error using less memory.
A theory result. No direct application yet.
Authors
Kuan Cheng, Ruiyang Wu
Abstract
We study SC derandomizations for regular read-once branching programs (ROBPs) and computation models beyond BPL. For regular ROBPs with length $n$, width $w$, and multiple accept nodes, we attain three results. 1. When $n \le w$, we show an SC derandomization with space $O(\log^2 n+\log w)$ and error $1/\text{poly}(nw)$. 2. When $n \ge w$, we show an SC derandomization with space $O(\log n \log w)$ and error $1/\text{poly}(w)$. 3. When $w=O(\log n)$, we show an optimal $O(\log n)$ space derandomization with error $1/\text{poly}(w)$. We further show that two super sets of BPL can be computed in SC. 1. For probabilistic logspace TMs with a two-way access random tape, we show that it can be approximated in SC if each entry of the random tape is accessed for at most a constant number of times. 2. For probabilistic logspace TMs with a polynomial size stack, i.e. probabilistic logspace Auxiliary Push-down Machines (AuxPDMs), we show that it can be approximated in SC if the timings of push/pop/idle stack operations do not depend on the randomness. The first model is the read-multiplicity model considered by Impagliazzo, Nisan, Wigderson (STOC'94), in which they show that their INW generator can fool such computations. For the second model, we indicate that it contains candidate languages separating BQL from BPL considered by Apers and Edenhofer (CCC'25).