A Forward-Backward Weight Analysis of INW for Permutation Branching Programs
cs.CC, cs.DS
Submitted: 2026-07-20
Updated: 2026-11-02
License: http://creativecommons.org/publicdomain/zero/1.0/
The gist: We construct an epsilon-error PRG for permutation read-once branching programs of length n and width w with seed length O ((w+ (1/epsilon)) times n).
Terminology
Abstract
We construct an epsilon-error PRG for permutation read-once branching programs of length n and width w with seed length O ((w+ (1/epsilon)) times n). 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/epsilon 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).
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?