Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

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 fool width-3 programs, constant-width regular programs, and unbounded-width permutation programs with a single accepting vertex. In all three cases, the seed length is $\widetilde{O}\left(\log n \cdot \sqrt{\log(1/\varepsilon)} + \log(1/\varepsilon)\right)$, where $n$ is the length of the program and $\varepsilon$ is the error of the WPRG.

For comparison, for all three of these models, the best explicit unweighted PRGs known have seed length $\widetilde{O}(\log n \cdot \log(1/\varepsilon))$ (Meka, Reingold, and Tal STOC 2019; Braverman, Rao, Raz, and Yehudayoff SICOMP 2014; Hoza, Pyne, and Vadhan ITCS 2021). Our WPRG seed length is superior when $\varepsilon$ is small. For the case of unbounded-width permutation programs, Pyne and Vadhan previously constructed a WPRG with a seed length that is similar to ours (CCC 2021), but their seed length has an extra additive $\log^{3/2} n$ term, so our WPRG is superior when $\varepsilon \gg 1/n$.

Our results are based on a new, general framework for error reduction. Our framework builds on the remarkable recent work by Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020) that gave a near-logarithmic space algorithm for estimating random walk probabilities in Eulerian digraphs with high precision. Our framework centers around the "inverse analysis" of random walks and a key combinatorial structure termed "shortcut graphs." Using our new framework and the recent notion of singular value approximation (Ahmadinejad, Peebles, Pyne, Sidford, and Vadhan arXiv 2023), we also present an alternative, simpler proof of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan's main theorem. Compared to the original proof, our new proof avoids much of the sophisticated machinery that was imported from recent work on fast Laplacian solvers.

A "pseudorandom generator" is an algorithm that makes a few coin tosses and outputs a long sequence of bits that "appear random" in some sense. A "weighted pseudorandom generator" is similar, except instead of working with actual probabilities, we work with "pseudoprobabilities," which are allowed to be positive or negative. Pseudoprobability is a little strange, but it turns out that for some purposes, weighted pseudorandom generators are just as useful as ordinary pseudorandom generators — and sometimes they are easier to design. This paper presents some new weighted pseudorandom generators that improve over prior work in terms of the number of coin tosses that they make.