BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1068
DTSTAMP:20230914T125949Z
SUMMARY:On Decision Tree Complexity of Boolean Functions
DESCRIPTION:Speaker: Swagato Sanyal (Indian Institute of Technology Kharagp
 ur\nKharagpur\, West Bengal)\n\nAbstract: \nTalk will be held on Zoom.\nAb
 stract: The decision tree model\, also known as the query model\, is a sim
 ple model of computation. Besides having an intuitive appeal\, and offerin
 g a natural paradigm for algorithm design\, it is often possible to theore
 tically nail down the exact complexity of many interesting algorithmic tas
 ks using currently available methods\, completely and unconditionally\; fo
 r more complex models of computation such an aspiration is currently a dis
 tant dream. In this talk we will first introduce and motivate query model\
 , and then present a recent work of ours on the query complexity of an imp
 ortant subclass of problems\, called composed functions. The latter part i
 s based on joint work with Dmitry Gavinsky\, Troy Lee and Miklos Santha wh
 ich has appeared in ICALP 2019.\n
URL:https://www.tcs.tifr.res.in/web/events/1068
DTSTART;TZID=Asia/Kolkata:20200707T140000
DTEND;TZID=Asia/Kolkata:20200707T150000
END:VEVENT
END:VCALENDAR