2026-08-03T01:04:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13546 2024-03-06T10:52:16Z ddc:004 open_access

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs Hoza, William M. Pyne, Edward Vadhan, Salil Pseudorandom generators permutation branching programs We prove that the Impagliazzo-Nisan-Wigderson [Impagliazzo et al., 1994] pseudorandom generator (PRG) fools ordered (read-once) 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 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 = 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 unbounded-width programs, showing that our seed length is near-optimal. 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 unit-circle approximation by Ahmadinejad et al. [Ahmadinejad et al., 2020]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik William M. Hoza and Edward Pyne and Salil Vadhan 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.7 urn:nbn:de:0030-drops-135464 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.7 eng https://creativecommons.org/licenses/by/3.0/legalcode