BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of California\, Berkeley//UCB Events Calendar//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
DTSTART:19701029T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:19700402T020000
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20160714T163240Z
X-ORACLE-EVENTTYPE:DAILY NOTE
DTSTART;VALUE=DATE:20170306
DTEND;VALUE=DATE:20170306
TRANSP:TRANSPARENT
SUMMARY:Proving and Using Pseudorandomness
RRULE:FREQ=DAILY;INTERVAL=1;UNTIL=20170310
UID:100870-ucb-events-calendar@berkeley.edu
ORGANIZER;CN="UC Berkeley Calendar Network":
LOCATION:Calvin Laboratory (Simons Institute for the Theory of Computing)
DESCRIPTION:One theme of this workshop will be how to leverage weak pseudorandomness properties\, fooling simple classes of tests\, in order to derive stronger pseudorandomness properties related to more complex tests. In the setting of additive combinatorics\, what is the minimal set of tests that primes have to satisfy in order to guarantee that they contain arithmetic progressions (or other structures)? For example\, recent work of Conlon\, Fox and Zhao shows that a “correlation condition” initially imposed in the work of Green and Tao is not necessary.\n \nIn complexity theory\, most unconditional constructions of pseudorandom generators ultimately all rely on various combinations of four basic tools: k-wise independence\, small-bias distributions\, error-correcting codes\, and random walks in expanders. The technical core of the analysis of known pseudorandom generators is to show that pseudorandomness against simple tests implies pseudorandomness against more complex tests (see for example Braverman’s theorem). Explicit constructions of pseudorandom objects have been essential to derandomize algorithms such as primality testing and undirected connectivity\, and they have been applied in cryptography\, distributed systems\, complexity theory\, streaming algorithms and learning theory. This workshop will explore unconditional constructions of pseudorandom objects at the frontier of progress\, such as pseudorandom generators for small-space computations\, small-depth circuits with modular gates\, threshold circuits and DNFs.\n\nOrganizers: \nDavid Conlon (University of Oxford)\, Raghu Meka (UCLA\; chair)\, Russell Impagliazzo (UC San Diego)\, Luca Trevisan (Simons Institute\, UC Berkeley).
URL:http://events.berkeley.edu/index.php/calendar/sn/pubaff.html?event_ID=100870&view=preview
SEQUENCE:0
CLASS:PUBLIC
CREATED:20160714T163240Z
LAST-MODIFIED:20160714T163240Z
X-UCBCN-ADMISSION:Registration Required\\nRegistration Info: online
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
X-MICROSOFT-CDO-INSTTYPE:0
X-MICROSOFT-CDO-IMPORTANCE:1
X-MICROSOFT-CDO-OWNERAPPTID:-1
END:VEVENT
END:VCALENDAR