Pseudodistributions That Beat All PRGsSpeaker: Ted
Title: Pseudodistributions That Beat All PRGs
Date: 15 Apr 2021 17:00-18:00 EST
Abstract: In 2018, Braverman, Cohen and Garg introduced the notion of weighted pseudorandom generators (WPRGs), a generalization of PRGs, and constructed WPRGs for read-once branching programs with near optimal dependence on error. This talk will present a recent paper constructing weighted PRGs for permutation branching programs that achieve parameters that are impossible to achieve with a PRG.