Hoza, William M. ;
Pyne, Edward ;
Vadhan, Salil
Pseudorandom Generators for UnboundedWidth Permutation Branching Programs
Abstract
We prove that the ImpagliazzoNisanWigderson [Impagliazzo et al., 1994] pseudorandom generator (PRG) fools ordered (readonce) permutation branching programs of unbounded width with a seed length of Õ(log d + log n ⋅ log(1/ε)), 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 ε is the error of the PRG. In contrast, we show that a randomly chosen generator requires seed length Ω(n log d) to fool such unboundedwidth 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 = poly(n) and d = 2, the best prior PRG for permutation branching programs was simply Nisan’s PRG [Nisan, 1992], which fools general ordered branching programs with seed length O(log(wn/ε) log n). We prove a seed length lower bound of Ω̃(log d + log n ⋅ log(1/ε)) for fooling these unboundedwidth programs, showing that our seed length is nearoptimal. In fact, when ε ≤ 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 [Rozenman and Vadhan, 2005] and the recent analysis of the latter in terms of unitcircle approximation by Ahmadinejad et al. [Ahmadinejad et al., 2020].
BibTeX  Entry
@InProceedings{hoza_et_al:LIPIcs.ITCS.2021.7,
author = {William M. Hoza and Edward Pyne and Salil Vadhan},
title = {{Pseudorandom Generators for UnboundedWidth Permutation Branching Programs}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {7:17:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13546},
URN = {urn:nbn:de:0030drops135464},
doi = {10.4230/LIPIcs.ITCS.2021.7},
annote = {Keywords: Pseudorandom generators, permutation branching programs}
}
04.02.2021
Keywords: 

Pseudorandom generators, permutation branching programs 
Seminar: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Issue date: 

2021 
Date of publication: 

04.02.2021 