Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Edward Pyne:

TR21-019 | 17th February 2021
Edward Pyne, Salil Vadhan

Pseudodistributions That Beat All Pseudorandom Generators

A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a pseudorandom pseudodistribution generator (PRPG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of PRPGs for ... more >>>

TR20-138 | 9th September 2020
William Hoza, Edward Pyne, Salil Vadhan

Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

Revisions: 1

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

ISSN 1433-8092 | Imprint