Lune

SODA2026Top-tier venue

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 nn and ww as the length and the width of an ROBP. We have the following results. For standard ROBPs, there exists an explicit ε\varepsilon-WPRG with seed length O(log⁡nlog⁡(nw)max⁡{1,log⁡log⁡w−log⁡log⁡n}+log⁡w(log⁡log⁡log⁡w−log⁡log⁡max⁡{2,log⁡wlog⁡n/ε})+log⁡(1/ε))O\left(\frac{\log n \log(nw)}{\max\{1,\log \log w - \log \log n\}} + \log w \left( \log \log \log w - \log \log \max\left\{2,\frac{\log w}{\log n/\varepsilon}\right\} \right) + \log(1/\varepsilon)\right). When n=wo(1)n = w^{o(1)}, this is better than the construction of Hoza (RANDOM 2022), and the construction of Cohen, Doron, Renard, Sberlo, and Ta-Shma (CCC 2021). Further, by using this in a black-box way, we attain a WPRG for regular ROBPs with seed length O(log⁡n(log⁡(1/ε)+log⁡w+log⁡log⁡n)+log⁡(1/ε))O\left( \log n \left( \sqrt{\log(1/\varepsilon)} + \log w + \log \log n \right) + \log(1/\varepsilon) \right), which slightly improves the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023). For permutation ROBPs with unbounded widths and single accept nodes, we give an explicit ε\varepsilon-WPRG with seed length O(log⁡n(log⁡log⁡n+log⁡(1/ε))+log⁡(1/ε))O\left( \log n \left( \log \log n + \sqrt{\log(1/\varepsilon)} \right) + \log(1/\varepsilon) \right), improving the result of Chen, Hoza, Lyu, Tal, and Wu (FOCS 2023). A key difference is that our result 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 ε\varepsilon with ε/w\varepsilon/w, this gives a WPRG with optimal seed length O(log⁡w)O(\log w) for n=2O(log⁡w)n = 2^{O(\sqrt{\log w})}, and error 1/poly⁡w1/\operatorname{poly} w. The only previous work attaining optimal seed lengths are Nisan-Zuckerman style PRGs which are only optimal for n=poly⁡log⁡wn = \operatorname{poly}\log w, ε=2−log⁡0.9w\varepsilon = 2^{-\log^{0.9} w}. For regular ROBPs with n≤2O(log⁡w)n \le 2^{O(\sqrt{\log w})}, ε=1/poly⁡(w)\varepsilon = 1/\operatorname{poly}(w), we give a derandomization within space O(log⁡w)O(\log w), i.e., in L\mathbf{L} exactly. When requiring the derandomization to be in L\mathbf{L}, the only previous result is again by Nisan-Zuckerman style PRGs, which can only handle n=poly⁡log⁡wn = \operatorname{poly}\log w, ε=2−log⁡0.9w\varepsilon = 2^{-\log^{0.9} w}. If compared to the result of Ahmadinejad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020), then for n=2O(log⁡w)n = 2^{O(\sqrt{\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 ww. All our results are based on iterative weighted pseudorandom reductions, which can iteratively reduce fooling long ROBPs to fooling short ones.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Approximating Iterated Multiplication of Stochastic Matrices in Small Space cites High-precision Estimation of Random Walks in Small Space
  • Singular Value Approximation and Sparsifying Random Walks on Directed Graphs cites High-precision Estimation of Random Walks in Small Space
  • Certified Hardness vs. Randomness for Log-Space cites High-precision Estimation of Random Walks in Small Space
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on6

  1. High-precision Estimation of Random Walks in Small SpaceAmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles et al.FOCS 2020 · 20 citations
  2. Singular Value Approximation and Sparsifying Random Walks on Directed GraphsAmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford et al.FOCS 2023 · 7 citations
  3. Certified Hardness vs. Randomness for Log-SpaceEdward Pyne, Ran Raz, Wei ZhanFOCS 2023 · 5 citations
  4. Approximating Iterated Multiplication of Stochastic Matrices in Small SpaceGil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-ShmaSTOC 2023 · 4 citations
  5. Near-Optimal Derandomization of Medium-Width Branching ProgramsAaron (Louie) Putterman, Edward PyneSTOC 2023 · 3 citations

Related papers

  1. Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and ShortcuttingLijie Chen, William M. Hoza, Xin Lyu, Avishay Tal et al.FOCS 2023 · 1 citation
  2. Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of PseudorandomnessJiatu Li, Edward Pyne, Roei TellFOCS 2024 · 3 citations
  3. Pseudorandom Hashing for Space-bounded Computation with Applications in StreamingPraneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. WoodruffFOCS 2023
  4. Nearly Optimal Pseudorandomness From HardnessDean Doron, Dana Moshkovitz, Justin Oh, David ZuckermanFOCS 2020 · 15 citations
  5. Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-WiseLijie Chen, Roei TellFOCS 2021 · 18 citations
Dusk over the sea between two cliffs drawn in fine vertical lines