Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909697723858944 |
|---|---|
| author | Cheng, Kuan Wu, Ruiyang |
| author_facet | Cheng, Kuan Wu, Ruiyang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08272 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions Cheng, Kuan Wu, Ruiyang Computational Complexity Data Structures and Algorithms 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. |
| title | Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.08272 |