SODA 2026 | 基于加权伪随机归约构造加权伪随机生成器

只读单次分支程序（ROBP）是一类分层的有向无环图模型，在计算能力上与对数空间的随机算法等价。近年，Braverman、Cohen 和 Garg 提出的加权伪随机生成器（WPRG）^[3]在 ROBP 去随机化研究中越来越受到关注。形式化地，一个   -WPRG 是一个函数   ，使得对于一类函数  ，我们有  输入长度   被称为该 WPRG 的种子长度。

把 ROBP 的层数计作 ，每层节点数计作 。在  的场景下，现有构造方法已能实现种子长度为  的高精度 WPRG^[7]。这相比于经典的 Nisan PRG^[9]，在种子长度上有显著提升。然而，在处理短-宽 ROBP，特别是  ，目标误差  的情景下，前人方法仍然无法突破  的种子长度瓶颈^[7,5]，与 Nisan PRG 的种子长度相当。如何在该情景下构造更高效的 WPRG，乃至于达到种子长度的理论下界  ，至今为止是一个重要的开放问题。

我们根据短-宽 ROBP 的特殊性，提出了加权伪随机归约（Weighted Pseudorandom Reduction）这一概念。具体而言，一个加权伪随机归约就是将一个 ROBP   的期望  近似表示为多个问题规模更小的子 ROBP   的加权  。通过递归地使用加权伪随机归约，可以将原始 ROBP 的期望拆分多个常数规模的子 ROBP 的加权和。随后，使用纯随机采样估计这些子 ROBP 的期望，并将结果加权求和。在加权伪随机归约足够显式时，可以将这一过程视作一种新的 WPRG 构造方法。

1. 长度归约能将长度为 ，宽度为  ，字母表为  的 ROBP，以  的误差近似为  个长度为 ，宽度为 ，字母表大小为 的 ROBP 的加权和。这一过程需要花费  的随机比特。

2. 字母表归约能将长度为  ，宽度为 ，字母表为  的 ROBP，以  的误差近似为多个长度为 ，宽度为 ，字母表大小为  的 ROBP 的加权和，其权重和为  。这一过程需要花费  的随机比特。

通过交替使用上述两种归约方法，我们只需要  轮归约，就能将长度为 ，宽度为  的 ROBP 以  精度近似为多个常数长度，宽度为 ，字母表大小为  的 ROBP 的加权和。在这样参数设定下，构造的 WPRG 的种子长度为，优于现有的 的种子长度。

二、置换 ROBP 是一种特殊的 ROBP，其层间转移函数为节点集合上的置换。针对置换 ROBP， 我们发现 Chen, Hoza, Lyu, Tal, 和 Wu 提出的 WPRG^[4]中用到的 Impagliazzo-Nisan-Wigderson（INW）生成器^[8]对于大字母表情形有最优的种子长度。具体来说，针对长度为 ，宽度为 ，字母表大小为  的置换 ROBP，INW 生成器能实现种子长度为  的  -PRG构造。此外，如果用我们提出的加权伪随机归约方法分析 Chen 等人的 WPRG 构造，可以将他们的 WPRG 视为一种从长度为 ，字母表为  的置换 ROBP 到长度为 ，字母表为  的置换 ROBP 的加权伪随机归约。其中，  是一个可调参数。

因此，我们利用这一发现构造了多轮的加权伪随机归约。通过选择合适的  （  ），我们可以在多轮迭代后使 ROBP 的长度缩短到常数，同时把字母表大小的增长控制在   内。最终，我们构造的 WPRG 的种子长度为  ，消除了 Chen 等人 WPRG 构造中的   乘子项。

正则 ROBP 是另一类特殊的 ROBP，其转移矩阵为双随机矩阵。通过应用我们提出的加权伪随机归约，我们还得出了针对正则 ROBP 的新 WPRG 以及在对数空间复杂度下去随机化短正则 ROBP 的算法。

一、对于正则 ROBP，我们将 Chen 等人提出的 WPRG^[4]视为一种从正则 ROBP 到短、宽、大字母表的一般 ROBP 的加权伪随机归约。随后，我们为归约后的 ROBP 构造了新的 WPRG，从而得到了对于原始正则 ROBP 的 WPRG 构造。这一构造同样消去了 Chen 等人 WPRG 中的  乘子项。

二、针对短正则 ROBP，也即  的情景，我们注意到对于置换 ROBP，我们的 WPRG 构造已经达到了  的种子长度，而正则 ROBP 的去随机化和置换 ROBP 的去随机化在复杂性上较为类似。因此，我们详细分析了对于置换 ROBP 的 WPRG 构造过程，并将其转化为了一个具有相似归约结构、相似参数设定和对数复杂度的去随机化算法。

本研究说明了加权伪随机归约在 WPRG 构造中的潜力。通过针对短-宽 ROBP 和置换 ROBP 的结构特性，设计了新的加权伪随机归约方法，并基于此提出了高效的 WPRG 构造。这些构造在种子长度上均优于现有方法，并在短正则 ROBP 的去随机化中实现了对数空间复杂度。然而，仍然有许多开放问题值得进一步探索：

• 是否能进一步优化短-宽 ROBP 的 WPRG 构造，达到理论最优的种子长度  ？

• 如何将加权伪随机归约方法推广到更广泛的 ROBP 类别，例如任意次序读取（arbitrary-order）的 ROBP？

• 加权伪随机归约方法是否能应用于其他随机化计算模型的去随机化问题？

[1]Ahmadinejad, A., Kelner, J., Murtagh, J., Peebles, J., Sidford, A., and Vadhan, S. High-precision Estimation of Random Walks in Small Space. In FOCS 2020, pp. 1295–1306.

[2] Armoni, R. On the Derandomization of Space-Bounded Computations. In Randomization and Approximation Techniques in Computer Science, Springer, pp. 47–59.

[3] Braverman, M., Cohen, G., and Garg, S. Pseudorandom pseudodistributions with near-optimal error for read-once branching programs. SIAM Journal on Computing 49, 5 (2019), STOC 18–242.

[4] Chen, L., Hoza, W. M., Lyu, X., Tal, A., and Wu, H. Weighted

Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. In FOCS 2023, pp. 1224–1239.

[5] Cohen, G., Doron, D., Renard, O., Sberlo, O., and Ta-Shma,

A. Error Reduction for Weighted PRGs Against Read Once Branching Programs. In CCC 2021, p. 22.

[6] Hoza, W. M. Recent Progress on Derandomizing Space-Bounded Computation.

[7] Hoza, W. M. Better Pseudodistributions and Derandomization for Space-Bounded Computation. In APPROX/RANDOM 2021.

[8] Impagliazzo, R., Nisan, N., and Wigderson, A. Pseudorandomness for network algorithms. In STOC 1994, pp. 356–364.

[9] Nisan, N. Pseudorandom generators for space-bounded computation.Combinatorica 12, 4, 449–461.

图文 | 吴睿洋

PKU 程宽课题组