BEGIN:VCALENDAR
METHOD:PUBLISH
VERSION:2.0
PRODID:-//Cornell U. Department of Computer Science//Brown Bag Seminar//EN
BEGIN:VEVENT
SUMMARY:Brown bag: Eshan Chattopadhyay
DESCRIPTION:Title: Pseudorandom generators from Fourier Bounds\nSpeaker:
Eshan Chattopadhyay\nAbstract: Pseudorandom generators (PRGs) are
objects that take a short random seed\, and stretches it to a much
longer string that looks random to a targeted computation class.
Constructing PRGs for interesting classes of functions is a central goal
in complexity theory. However\, the state-of-art constructions of PRGs
are far-off from our derandomization goals (e.g.\, proving every
polynomial time randomized algorithm can be turned into a deterministic
algorithm a.k.a. proving P=BPP).\n\nIn this talk\, I will describe a new
framework for constructing PRGs that provides a unified construction for
various important complexity classes such as constant depth circuits
(AC0)\, algorithms with limited memory (read-once branching programs)\,
low-sensitivity functions\, etc. A tantalizing possibility of this
approach is a PRG for the class of constant depth circuits that also
contain parity gates (ACO[Mod 2])--a complexity class that is just
beyond AC0 but no known PRG exists with less than seed length 0.99n.\nI
will conclude with a few open problems that comes out of this new
approach.\n\nBased on joint works with Pooya Hatami\, Kaave Hosseini\,
Shachar Lovett\, and Avishay Tal.
LOCATION:Gates 122
UID:2018-09-18
STATUS:TENTATIVE
DTSTART:20180918T160000Z
DTEND:20180918T170000Z
LAST-MODIFIED:20180913T192315Z
ORGANIZER;CN=Jonathan Shi:http://www.cs.cornell.edu/~jshi/brownbag/
DTSTAMP:20240222T070037Z
END:VEVENT
END:VCALENDAR