BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Ical
BEGIN:VTIMEZONE
TZID:Asia/Jerusalem
BEGIN:STANDARD
DTSTART:20171029T020000
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:IST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20180323T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:IDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.50825.field_date.0@mathematics.huji.ac.il
DTSTAMP:20191116T232436Z
CREATED:20180114T110007Z
DESCRIPTION:Date: \n\n(All day)\n\n\n\n\nSee also: HD-Combinatorics\, Event
s & Seminars\, SeminarsLocation: \n\nRoom 130\, IIAS\, Feldman Building\,
Givat Ram\n\n\nAll talks will be given by Amnon Ta-Shma.10:00-11:00 - The
sampling problem and some equivalent formulations11:30-12:30 - A basic 'co
mbinatorial' construction14:00-14:45 - Algebraic constructions of randomne
ss condensers15:15-16:00 - Structured samplingProgram:1. 10:00-11:00 - The
sampling problem and some equivalent formulations. Abstract:We will first
define Samplers\, and the parameters thatone usually tries to optimize: a
ccuracy\, confidence\, query complexityand random bit complexity. We will
see how random walks on expandersfare with this\, compared with the optima
l\, non-explicit solution. We willthen see an almost-equivalence with rand
omness extractors\, and statewhat is known about explicit constructions of
randomness extractors. Wewill also see a similar equivalence between mult
iplicative-errorsamplers and condensers.2. 11:30-12:30 - A basic 'combinat
orial' constructionAbstract:I will present Trevisan's extractor. We will f
irst see an equivalence between one output bitstrong randomness extractors
and list-decodable error correcting codes.If time permits we will see how
to extend this to many output bits usingideas from pseudo-random generato
rs (PRGs). We will also discuss aconnection between PRGs and certain type
of randomness extractors(reconstructive randomness extractors)3. 14:00- 14
:45 - Algebraic constructions of randomness condensersAbstract:We will see
two algebraic constructions of randomness condensers: The GUV (Guruswami\
,Umans\, Vadhan) condenser using extension fields\, and Zuckerman'sconstan
t seed length somewhere random condenser building on additivenumber theory
. I will also mention some open problems.4. 15:15-16:00 Structured samplin
gAbstract:We will mention several applications where more is required from
the sampler beyond the obvious properties: Reingold's undirected connecti
vity in Logspace\, Rozenman and Vadhan derandomizedsquaring\, Dinur's PCP
theorem\, Dinur and Kaufmann's double samplers.Random objects do not give
structured sampling\, and it seems that highdimensional expanders do give
structured sampling.\n\n Export\n \n\n \nsubscribe iCal
DTSTART;VALUE=DATE:20180305
DTEND;VALUE=DATE:20180306
LAST-MODIFIED:20180301T000004Z
SUMMARY:HD-Combinatorics Special Day: Samplers in Computer Science (organiz
ed by Amnon Ta-Shma)
URL;TYPE=URI:https://mathematics.huji.ac.il/event/hd-combinatorics-special-
day-samplers-computer-science-organised-amnon-ta-shma
END:VEVENT
END:VCALENDAR