BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
PRODID:-//Fastmail/2020.5/EN
X-APPLE-CALENDAR-COLOR:#F64F00
X-WR-CALNAME:ComplexityReadingGroup
X-WR-TIMEZONE:Asia/Kolkata
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
DTSTART:19700101T000000
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DESCRIPTION:TITLE: Pseudorandom generators from polarizing random walks \nS
 PEAKER: Shachar Lovett \n\nAbstract: We propose a new framework for constr
 ucting pseudorandom \ngenerators for n-variate Boolean functions. It is ba
 sed on two new \nnotions. First\, we introduce fractional pseudorandom gen
 erators\, which \nare pseudorandom distributions taking values in [−1\,1]^
 n . Next\, we \nuse a fractional pseudorandom generator as steps of a rand
 om walk in \n[−1\,1]^n that converges to {-1\,1}^n . We prove that this ra
 ndom walk \nconverges fast (in time logarithmic in n) due to polarization.
  As an \napplication\, we construct pseudorandom generators for Boolean \n
 functions with bounded Fourier tails. We use this to obtain a \npseudorand
 om generator for functions with sensitivity s\, whose seed \nlength is pol
 ynomial in s. Other examples include functions computed \nby branching pro
 grams of various sorts or by bounded depth circuits. \n\nVIDEO: https://ww
 w.youtube.com/watch?v=4XExVwo89eo
DTEND;TZID=Asia/Kolkata:20181123T171500
DTSTAMP:20181123T032157Z
DTSTART;TZID=Asia/Kolkata:20181123T160000
SEQUENCE:0
SUMMARY:Shachar Lovett on PRGs from Polarising random walks
TRANSP:OPAQUE
UID:60742B37-24B7-4738-9FF4-30E7A78C3182
END:VEVENT
BEGIN:VEVENT
DESCRIPTION:Tutorial on 2-to-2 Conjecture\nhttps://www.birs.ca/events/2018/
 5-day-workshops/18w5197/videos/watch/201808130907-Kindler.html
DTEND;TZID=Asia/Kolkata:20181010T180000
DTSTAMP:20181010T132759Z
DTSTART;TZID=Asia/Kolkata:20181010T163000
SEQUENCE:0
SUMMARY:Guy Kindler on 2-to-2 Conjecture
TRANSP:OPAQUE
UID:76325C4A-20DC-4726-B257-1C5EC684920C
END:VEVENT
BEGIN:VEVENT
DESCRIPTION:Abstract: \nWe give an explicit black-box problem that can be s
 olved by a bounded-error quantum polynomial-time algorithm (BQP\, in short
 )\, but cannot be solved by a classical algorithm in the polynomial hierar
 chy.\n\nFollowing the approach of Aaronson [STOC\, 2010]\, our result is o
 btained by finding a distribution D over Boolean strings of length N such 
 that:\n(1) There exists a quantum algorithm that runs in time polylog(N) a
 nd distinguishes between D and the uniform distribution over Boolean strin
 gs of length N.\n(2) No Boolean circuit of quasi-polynomial size and const
 ant depth can distinguish between D and the uniform distribution with adva
 ntage better than polylog(N)/sqrt(N).\n\nJoint work with Ran Raz.\nhttps:/
 /simons.berkeley.edu/talks/tbd-11
DTEND;TZID=Asia/Kolkata:20181128T180000
DTSTAMP:20181127T132505Z
DTSTART;TZID=Asia/Kolkata:20181128T163000
SEQUENCE:0
SUMMARY:Avishay Tal on Oracle Separation between BQP and PH
TRANSP:OPAQUE
UID:89136ECE-EBD5-47C7-AD75-35080B3CDBD8
END:VEVENT
BEGIN:VEVENT
DESCRIPTION:https://www.birs.ca/events/2018/5-day-workshops/18w5197/videos/
 watch/201808161634-Lovett.html
DTEND;TZID=Asia/Kolkata:20181017T180000
DTSTAMP:20181010T133014Z
DTSTART;TZID=Asia/Kolkata:20181017T163000
SEQUENCE:0
SUMMARY:Shachar Lovett on GM-MDS Conjecture
TRANSP:OPAQUE
UID:A40B1794-3021-4D58-AC3E-F665372533C8
END:VEVENT
BEGIN:VEVENT
DESCRIPTION:Tutorial on 2-to-2 Conjecture\nhttps://www.birs.ca/events/2018/
 5-day-workshops/18w5197/videos/watch/201808130907-Kindler.html
DTEND;TZID=Asia/Kolkata:20181003T180000
DTSTAMP:20181010T132752Z
DTSTART;TZID=Asia/Kolkata:20181003T163000
SEQUENCE:0
SUMMARY:Guy Kindler on 2-to-2 Conjecture
TRANSP:OPAQUE
UID:C7C6D70E-4D1B-4D93-AAFE-3D95EEA5080D
END:VEVENT
END:VCALENDAR