BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Ashoka University - ECPv6.18.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Ashoka University
X-ORIGINAL-URL:https://www.ashoka.edu.in
X-WR-CALDESC:Events for Ashoka University
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20230427T140000
DTEND;TZID=Asia/Kolkata:20230427T150000
DTSTAMP:20230426T020903Z
CREATED:20230421T004226Z
LAST-MODIFIED:20230426T020903Z
UID:43044-1682604000-1682607600@www.ashoka.edu.in
SUMMARY:Sensitivity and computational complexity of Boolean functions
DESCRIPTION:Abstract:  \nLet f:{0\,1}^n -> {0\,1} be a Boolean function. We will discuss the connection between various notions of complexity associated with f: its sensitivity\, block sensitivity\, degree\, approximate degree\, and decision tree depth. We will present the recent breakthrough of Hao Huang (2019) who showed that  if f cannot be represented by a polynomial of low degree then it must be highly sensitive.  Finally\, we will show a new upper bound on the size of the deterministic decision tree computing f in terms of the size of  the corresponding randomized decision tree. The last result is from a recent joint work with Arkadev Chattopadhyay\, Yogesh Dahia\, Nikhil Mande and Swagato Sanyal. The talk will be accessible to a general scientific audience; we will assume nothing beyond basic linear algebra and combinatorics.  \nAbout the Speaker: \nJaikumar Radhakrishnan is a theoretical computer scientist with research interests in complexity theory\, randomness and computation\, quantum information and computation\, combinatorics\, and information theory. Radhakrishnan obtained his BTech in Computer Science and Engineering from IIT Kharagpur in 1991\, and his PhD in Computer Science from Rutgers University\, NJ\, USA\, in 1991.  He joined the Tata Institute of Fundamental Research in 1991\, where is currently a senior professor at the School of Technology and Computer Science (STCS)\, TIFR\, Mumbai\, and at the International Centre for Theoretical Sciences (ICTS-TIFR)\, Bengaluru. 
URL:https://www.ashoka.edu.in/event/sensitivity-and-computational-complexity-of-boolean-functions/
END:VEVENT
END:VCALENDAR