A Forward-Backward Weight Analysis of INW for Permutation Branching Programs
2026-07-20 • Computational Complexity
Computational ComplexityData Structures and Algorithms
AI summaryⓘ
The authors create a new pseudorandom generator (PRG) that efficiently simulates permutation read-once branching programs, improving how the seed length depends on the program's width and length. Their approach uses a known generator (the INW PRG) combined with special expander graphs whose properties don't depend on the program length, which is a new insight. By analyzing error in a precise, program-specific way, they prevent errors from piling up as the generator runs. Their results improve on past work by reducing seed length while matching theoretical limits based on spectral graph properties.
pseudorandom generatorpermutation branching programseed lengthread-once branching programINW generatorexpander graphsspectral expansionerror analysisseminorms
Authors
Gil Cohen, Dean Doron, Noam Goldgraber
Abstract
We construct an $\varepsilon$-error PRG for permutation read-once branching programs of length $n$ and width $w$ with seed length \[ O\left((\log w+\log(1/\varepsilon))\cdot \log n\right). \] This gives an exponential improvement in the dependence on $w$ compared with the constructions of De (CCC 2011) and Steinke (ECCC 2012). Compared with the work of Braverman, Rao, Raz, and Yehudayoff (FOCS 2010; SICOMP 2014), which applies more generally to regular branching programs and already achieves the optimal dependence on $w$, our result improves the dependence on the length $n$, attaining the optimal logarithmic dependence. The generator itself is the classical INW PRG of Impagliazzo, Nisan, and Wigderson (STOC 1994). We show that, for permutation branching programs, the INW generator can be instantiated with expanders whose degrees are polynomial in $w$ and $1/\varepsilon$ and, crucially, independent of $n$. To prove this, we analyze error propagation using program-dependent seminorms tailored to the branching program at hand. These seminorms build on the weight function introduced by Braverman et al. The key point is that, when measured in these adapted seminorms, the error does not accumulate throughout the recursion. Since our analysis relies only on the spectral expansion of the underlying expanders, our seed length tightly matches the recent lower bound for spectral analyses of the INW generator due to Hoza, Pyne, and Vadhan (Algorithmica 2024).