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:20200308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20201101T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69d3ef1f88d2e
DTSTART;TZID=America/Toronto:20201123T113000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20201123T113000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-gr
 aph-theory-seminar-nathan-lindzey-3
SUMMARY:Algebraic Graph Theory Seminar - Nathan Lindzey
CLASS:PUBLIC
DESCRIPTION:TITLE: Complexity Measures on the Symmetric Group and Beyond\n
 \nSpeaker:\n Nathan Lindzey\n\nAffiliation:\n CU Boulder\n\nZoom:\n Contac
 t Soffia Arnadottir\n\nABSTRACT:\n\nA classical result in complexity theor
 y states that a degree-d Boolean\nfunction on the hypercube can be compute
 d using a decision tree of\ndepth poly(d). Conversely\, a Boolean function
  computed by a decision\ntree of depth d has degree at most d. Thus degree
  and decision tree\ncomplexity are polynomially related. Many other comple
 xity measures of\nBoolean functions on the hypercube are polynomially rela
 ted to the\ndegree (e.g.\, approximate degree\, certificate complexity\, b
 lock\nsensitivity)\, and last year Huang famously added sensitivity to the
 \nlist. Can we prove similar results for Boolean functions on other\ncombi
 natorial domains?
DTSTAMP:20260406T173631Z
END:VEVENT
END:VCALENDAR