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 $\varepsilon$-WPRG with seed length
$$O\left(\frac{\log n\log (nw)}{\max\left\{1,\log\log w-\log\log n\right\}}+\log w \left(\log\log\log w-\log\log\max\left\{2,\frac{\log w}{\log \frac{n}{\varepsilon}}\right\}\right)+\log\frac{1}{\varepsilon}\right).$$
For permutation ROBPs with unbounded widths and single accept nodes, we give an explicit $\varepsilon$-WPRG with seed length
$$O\left( \log n\left( \log\log n + \sqrt{\log(1/\varepsilon)} \right)+\log(1/\varepsilon)\right). $$
We also give a new Nisan-Zuckerman style derandomization for regular ROBPs with width $w$, length $n = 2^{O(\sqrt{\log w})}$, and multiple accept nodes. We attain optimal space complexity $O(\log w)$ for arbitrary approximation error $\varepsilon = 1/\text{poly} (w)$.
All our results are based on iterative weighted pseudorandom reductions, which can iteratively reduce fooling long ROBPs to fooling short ones.
From: Ruiyang Wu [view email]
[v1]
Wed, 12 Feb 2025 10:27:18 UTC (39 KB)
[v2]
Sun, 25 May 2025 02:41:37 UTC (295 KB)
[v3]
Thu, 17 Jul 2025 08:59:20 UTC (111 KB)
[v4]
Mon, 21 Jul 2025 13:15:56 UTC (111 KB)
[v5]
Fri, 10 Jul 2026 08:44:27 UTC (114 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。