BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20210314T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20201101T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69d1e941b281c
DTSTART;TZID=America/Toronto:20210414T130000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20210414T130000
URL:https://uwaterloo.ca/computer-science/events/seminar-algorithms-and-com
 plexity-an-optimal-separation-of-randomized-and-quantum-query-complexity
LOCATION:200 University Avenue West Online seminar Waterloo ON N2L 3G1 Cana
 da
SUMMARY:Seminar • Algorithms and Complexity — An Optimal Separation of\
 nRandomized and Quantum Query Complexity
CLASS:PUBLIC
DESCRIPTION:PLEASE NOTE: THIS SEMINAR WILL BE GIVEN ONLINE.\n\nPEI WU\, CO
 MPUTER SCIENCE DEPARTMENT\n_University of California\, Los Angeles_\n\nWe 
 prove that for every decision tree\, the absolute values of the\nFourier c
 oefficients of given order $\\ell\\geq1$ sum to at most\n$c^{\\ell}\\sqrt{
 \\binom{d}{\\ell}(1+\\log n)^{\\ell-1}}\,$ where $n$ is the\nnumber of var
 iables\, $d$ is the tree depth\, and $c>0$ is an absolute\nconstant. This 
 bound is essentially tight and settles a conjecture due\nto Tal (arxiv 201
 9\; FOCS 2020). 
DTSTAMP:20260405T044657Z
END:VEVENT
END:VCALENDAR