All reports by Author Edward Pyne:

__
TR20-138
| 9th September 2020
__

William Hoza, Edward Pyne, Salil Vadhan#### Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

William Hoza, Edward Pyne, Salil Vadhan

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 ... more >>>