Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
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{\lo...
Guardat en:
| Autors principals: | , |
|---|---|
| Format: | Article |
| Publicat: |
2025
|
| Matèries: | |
| Accés en línia: | https://arxiv.org/abs/2502.08272 http://arxiv.org/abs/2502.08272 |
| Etiquetes: |
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|