Revised: September 17, 2025
Published: June 8, 2026
Abstract: [Plain Text Version]
A recent paper of Braverman, Cohen, and Garg (STOC'18) introduced the concept of a weighted pseudorandom generator (WPRG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with (potentially negative) real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of WPRGs for ordered branching programs whose seed length has a better dependence on the error parameter $\eps$ than the classic PRG construction of Nisan (STOC'90 and Combinatorica 1992). In this article we give an explicit construction of WPRGs that achieve parameters that are impossible to achieve by a PRG. In particular, we construct a WPRG for ordered permutation branching programs of unbounded width with a single accept state that has seed length $\tO(\log^{3/2} n)$ for error parameter $\eps=1/\poly(n)$, where $n$ is the input length. In contrast, recent work of Hoza et al. (ITCS'21) shows that any PRG for this model requires seed length $\Omega(\log^2 n)$ to achieve error $\eps=1/\poly(n)$. As a corollary, we obtain explicit WPRGs with seed length $\tO(\log^{3/2} n)$ and error $\eps=1/\poly(n)$ for ordered permutation branching programs of width $w=\poly(n)$ with an arbitrary number of accept states. Previously, seed length $o(\log^2 n)$ was only known when both the width and the reciprocal of the error are subpolynomial, i.e., $w=n^{o(1)}$ and $\eps=1/n^{o(1)}$ (Braverman, Rao, Raz, Yehudayoff, FOCS'10 and SICOMP 2014). The starting point for our work was the recent family of space-efficient algorithms for estimating random-walk probabilities in directed graphs by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS'20), which are based on spectral graph theory and space-efficient Laplacian solvers. We interpret these algorithms as giving WPRGs with large seed length, which we then derandomize to obtain our results. We also note that this approach gives a simpler proof of the original result of Braverman, Cohen, and Garg, as independently discovered by Cohen, Doron, Renard, Sberlo, and Ta-Shma (CCC'21).
--------------
An extended abstract of this paper appeared in the Proceedings of the 36th Computational Complexity Conference (CCC’21).
Licensed under a Creative Commons Attribution License (CC-BY)