BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Extractors for Samplable Distributions from the Two-Source Extract
 or Recipe - Justin Oh (UT Austin)
DTSTART:20250919T090000Z
DTEND:20250919T100000Z
UID:TALK235531@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:A natural model of the sources of randomness one might enginee
 r or obtain in nature is the samplable distribution. Such a distribution i
 s generated by an efficient algorithm or circuit\, but may not have much r
 andomness overall\, e.g. may not have much entropy. Trevisan and Vadhan [T
 V00] first introduced this notion\, and showed under strong complexity the
 oretic assumptions that it is possible to *extract* from such sources. Tha
 t is\, there is an algorithm (an *extractor*) to convert such a distributi
 on into a nearly uniform distribution\, which can then be used in applicat
 ions such as randomized algorithms and cryptography.\n\nThere has been rec
 ently renewed interest in this problem\, with various recent results build
 ing off the initial techniques of [TV00]. The two main questions to addres
 s are:\nWhat is the weakest complexity theoretic assumption required to co
 nstruct the extractor?\nWhat is the smallest amount of entropy required of
  the original distribution?\nIn this work\, we present a new technique for
  constructing extractors for samplable distributions\, that works for esse
 ntially the lowest possible entropy required of the original distribution\
 , and using a "qualitatively" weaker assumption than previous works (albei
 t technically incomparable). Our work introduces a connection between our 
 problem and the breakthrough construction of two-source extractors by Chat
 topadhyay and Zuckerman. The approach also provides a novel and direct app
 lication of pseudorandom generators\, a ubiquitous tool in areas such as d
 erandomization.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR