Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions

Jul 16, 2026

3

0

Upload by Logic

研究加权伪随机生成器（WPRG）及其对只读分支程序（ROBPs）的去随机化。设ROBPs长度为n、宽度为w。给出标准ROBPs的显式ε-WPRG及其种子长度上界，并在n=w^{o(1)}时优于若干既有WPRG结果；对规则ROBPs作为直接应用得到更优的种子长度。对置换ROBPs给出改进的显式ε-WPRG；差异在于还能推出多接受节点短-宽ROBPs的最优种子长度。进一步提供规则ROBPs的Nisan-Zuckerman风格去随机化，并在空间与时间复杂度上优于相关工作。所有结果基于迭代加权伪随机归约。

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages49

Reading Time2 h 3 min

Table of Contents

Introduction

Read-once branching programs (ROBP)

Pseudorandom generators (PRG)

Weighted pseudorandom generators

arXiv :2502 .08272v 5 [ cs .CC] 10 Jul 2026 Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions Kuan Cheng ∗ Ruiyang Wu † Abstract We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs) . Denote n and w as the length and the width of a ROBP. We have the following results. For standard ROBPs, we give an explicit ε-WPRG with seed length O 􀀒 max{1,~~ ~~llooggnlologgw(lo)~~ ~~g~~ ~~log~~ ~~n} + log w 􀀒log log log w − log log max 􀀚 2 , loglog~~ ~~w~~n~~ε 􀀛􀀓 + log 1ε􀀓 . When n = wo(1), this is better than the WPRGs of [Hoz21, CDR+ 21 , PV21 , CL20] . Further asa direct application, we attain a WPRG for regular ROBPs with a better seed length than that of [CHL+ 23 , CL24] . For permutation ROBPs with unbounded widths and single accept nodes, we give an explicit ε-WPRG with seed length O 􀀐log n 􀀐log log n +plog(1/ε)􀀑 + log(1/ε)􀀑 , improving [CHL+ 23] . A key difference to [CHL+ 23] is that this implies a WPRG with optimal seed length for short-wide ROBPs with multiple accept nodes. Specifically, after switching to multiple accept nodes in a standard way by replacing ε with ε/w, this gives a WPRG with optimal seed length O(log w) for n = 2O ( √log w) , and error 1/poly w. The only previous work attaining optimal seed lengths are Nisan-Zuckerman style PRGs [NZ96, Arm98] but they are only optimal for n = poly log w,ε = 2− log0.9 w . We also give a new Nisan-Zuckerman style derandomization for regular ROBPs with width w , length n = 2O ( √log w) , and multiple accept nodes. We attain optimal space complexity O (log w) for arbitrary approximation error ε = 1/poly w. When requiring the derandomization to be in L, again the only previous result is by Nisan-Zuckerman style PRGs [NZ96, Arm98], which are only optimal for n = poly log w,ε = 2− log0.9 w . Also, if compared to [AKM+ 20 , CHL+ 23 , CL24], which can be viewed as Saks-Zhou style derandomizations, then for n = 2O ( √log w) our derandomization not only improves the space complexity to optimal, but also substantially improves the time complexity from super polynomial to standard polynomial in w. Note that derandomizationsof [AKM+ 20 , CHL+ 23 , CL24] has space complexity S = O (log(nw)log log (nw/ε)) and time complexity exponential in S. All our results are based on iterative weighted pseudorandom reductions, which can iteratively reduce fooling long ROBPs to fooling short ones. ∗ CFCS, School of Computer Science, [Peking University. ckkcdh@pku.edu.cn](Peking University. ckkcdh@pku.edu.cn). †CFCS, School of Computer Science, [Peking University. wuruiyang@stu.pku.edu.cn](Peking University. wuruiyang@stu.pku.edu.cn). 1 Introduction. Randomness is a fundamental resource in computation, but is it essential? A key conjecture in space-bounded computation is that randomized algorithms in the complexity class BPL can be efficiently simulated by deterministic logspace algorithms, i.e. BPL = L. A central approach toward addressing this conjecture is the derandomization of standard-order read-once branching programs (ROBPs), which is usually defined as the following. Definition 1.1 (Read-once branching programs (ROBP)) . A read-once branching program f of length n, width w and alphabet size |Σ| = 2s is a directed acyclic graph with n + 1 layers V0 ,..., Vn . For any layer Vi except Vn, each node v ∈ Vi has 2s outgoing edges to nodes in Vi+1 . These edges are labeled by distinct symbols in Σ . There exists a unique start node vstart ∈ V0 and a set of accept nodes Vaccept ⊂ Vn . Given an input x ∈ Σn , the computation of f (x) is defined as: f (x) = 1, if there exists a unique path vstart, v1 , . . . , vn such that the edge between vi and vi+1 is labeled by xi , and vn ∈ Vaccept; f (x) = 0 otherwise. Every problem in BPL can be reduced to approximating Ef for a corresponding ROBP f. A classical method for derandomizing ROBPs is constructing pseudorandom gene

FAQs

本文研究的核心对象是什么？

本文研究加权伪随机生成器（WPRG）以及其对只读分支程序（ROBPs）的去随机化。文中讨论标准ROBPs、规则ROBPs以及置换ROBPs等模型。

WPRG与PRG在本文中的定位关系是什么？

PRG用于通过伪随机性近似ROBPs的期望输出，而本文强调WPRG是另一种黑箱去随机化工具，并给出显式构造与种子长度改进。

本文结果的关键方法是什么？

文中所有主要结果都基于迭代加权伪随机归约：通过不断把“更长”的ROBPs归约为“更短”的对象来实现对长模型的逼近。

本文的主要改进体现在什么复杂度指标上？

对构造而言，重点改进WPRG的显式种子长度；对去随机化而言，重点提升空间复杂度到最优量级，同时在特定参数范围内把时间复杂度从超多项式改进为标准多项式。

Jul 16, 2026

3

0

Upload by Logic