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

Kuan Cheng; Ruiyang Wu

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR25-027 | 9th February 2025 17:24

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

TR25-027 Authors: Kuan Cheng, Ruiyang Wu
Publication: 12th March 2025 02:36
Downloads: 185

Keywords:

deradomization, permutation branching programs, read once branching programs, Regular Branching Programs, weighted pseudorandom generator

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