Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-138 | 1st December 2020 21:02

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

RSS-Feed




Revision #1
Authors: William Hoza, Edward Pyne, Salil Vadhan
Accepted on: 1st December 2020 21:02
Downloads: 577
Keywords: 


Abstract:

We prove that the Impagliazzo-Nisan-Wigderson (STOC 1994) pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of $\widetilde{O}(\log d + \log n \cdot \log(1/\varepsilon))$, assuming the program has only one accepting vertex in the final layer. Here, $n$ is the length of the program, $d$ is the degree (equivalently, the alphabet size), and $\varepsilon$ is the error of the PRG. In contrast, we show that a randomly chosen generator requires seed length $\Omega(n \log d)$ to fool such unbounded-width programs. Thus, this is an unusual case where an explicit construction is "better than random."

Except when the program's width $w$ is very small, this is an improvement over prior work. For example, when $w = \text{poly}(n)$ and $d = 2$, the best prior PRG for permutation branching programs was simply Nisan's PRG (Combinatorica 1992), which fools general ordered branching programs with seed length $O(\log(wn/\varepsilon) \log n)$. We prove a seed length lower bound of $\widetilde{\Omega}(\log d + \log n \cdot \log(1/\varepsilon))$ for fooling these unbounded-width programs, showing that our seed length is near-optimal. In fact, when $\varepsilon \leq 1 / \log n$, our seed length is within a constant factor of optimal. Our analysis of the INW generator uses the connection between the PRG and the derandomized square of Rozenman and Vadhan (RANDOM 2005) and the recent analysis of the latter in terms of unit-circle approximation by Ahmadinejad et al. (FOCS 2020).



Changes to previous version:

Minor improvements to presentation


Paper:

TR20-138 | 9th September 2020 04:29

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs





TR20-138
Authors: William Hoza, Edward Pyne, Salil Vadhan
Publication: 13th September 2020 06:39
Downloads: 1107
Keywords: 


Abstract:

We prove that the Impagliazzo-Nisan-Wigderson (STOC 1994) pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of $\widetilde{O}(\log d + \log n \cdot \log(1/\varepsilon))$, assuming the program has only one accepting vertex in the final layer. Here, $n$ is the length of the program, $d$ is the degree (equivalently, the alphabet size), and $\varepsilon$ is the error of the PRG. In contrast, we show that a randomly chosen generator requires seed length $\Omega(n \log d)$ to fool such unbounded-width programs. Thus, this is an unusual case where an explicit construction is "better than random."

Except when the program's width $w$ is very small, this is an improvement over prior work. For example, when $w = \text{poly}(n)$ and d = 2, the best prior PRG for permutation branching programs was simply Nisan's PRG (Combinatorica 1992), which fools general ordered branching programs with seed length $O(\log(wn/\varepsilon) \log n)$. We prove a seed length lower bound of $\widetilde{\Omega}(\log d + \log n \cdot \log(1/\varepsilon))$ for fooling these unbounded-width programs, showing that our seed length is near-optimal. In fact, when $\varepsilon \leq 1 / \log n$, our seed length is within a constant factor of optimal. Our analysis of the INW generator uses the connection between the PRG and the derandomized square of Rozenman and Vadhan (RANDOM 2005) and the recent analysis of the latter in terms of unit-circle approximation by Ahmadinejad et al. (FOCS 2020).



ISSN 1433-8092 | Imprint