A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs ... more >>>

In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian perspective of space-bounded derandomization, which was originally introduced by Ahmadinejad, Kelner, ... more >>>

Error reduction procedures play a crucial role in constructing weighted PRGs [PV'21, CDRST'21], which are central to many recent advances in space-bounded derandomization. The fundamental method driving error reduction procedures is the Richardson iteration, which is adapted from the literature on fast Laplacian solvers. In the context of space-bounded derandomization, ... more >>>

We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs), which are key problems towards answering the fundamental open question $\mathbf{BPL} ?{=} \mathbf{L}$.
Denote $n$ and $w$ as the length and the width of a ROBP.
We have the following results.

For standard ROBPs, there exists an ... more >>>