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. In this talk, we present new explicit constructions of WPRGs that fool certain types of space-bounded computation.

We focus on two classes of standard-order read-once branching programs, namely width-3 programs and constant-width regular programs. In both cases, we are able to construct an explicit WPRG with seed length O˜(logn⋅log(1/ε)‾‾‾‾‾‾‾√+log(1/ε)), where n is the length of the program and ε is the error of the WPRG. For comparison, for both of these models, the best explicit unweighted PRGs known have seed length O˜(logn⋅log(1/ε)) (Meka, Reingold, and Tal STOC 2019; Braverman, Rao, Raz, and Yehudayoff SICOMP 2014). Our WPRG seed length is superior when ε is small.

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."

Based on joint work with Lijie Chen, Xin Lyu, Avishay Tal, and Hongxun Wu (https://eccc.weizmann.ac.il/report/2023/114/).