Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-027 | 9th February 2025 17:24

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions

RSS-Feed

Abstract:

We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs), which are key problems towards answering the fundamental open question $\mathbf{BPL} ?{=} \mathbf{L}$.
Denote $n$ and $w$ as the length and the width of a ROBP.
We have the following results.

For standard ROBPs, there exists 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 n/\varepsilon}\right\}\right)+\log(1/\varepsilon)\right).$$
When $n = w^{o(1)}$, this is better than the constructions in [Hoz21, CDR+21, PV21, CL20]..

For permutation ROBPs with unbounded widths and single accept nodes, there exists an explicit $\varepsilon$-WPRG with seed length
$$ O\left( \log n\left( \log\log n + \sqrt{\log(1/\varepsilon)} \right)+\log(1/\varepsilon)\right). $$
This slightly improves the result of [CHL+23].

For regular ROBPs with $n \le 2^{O(\sqrt{\log w})}, \varepsilon = 1/\poly w$, we give a derandomization within space $O(\log w)$, i.e. in $\mathbf{L}$ exactly.
This is better than previous results of [AKM+20 , CHL+23 , CL24 ] in this regime.

Our main method is based on a recursive application of weighted pseudorandom reductions, which is a natural notion that is used to simplify ROBPs.



ISSN 1433-8092 | Imprint