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:20260408T153628Z
END:VEVENT
END:VCALENDAR