BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1722
DTSTAMP:20260525T083615Z
SUMMARY:Polynomial Time Local Decision Revisited
DESCRIPTION:Speaker: Soumyadeep Paul (TIFR)\n\nAbstract: \nWe consider hier
 archies related to distributed decision problems: unbounded computation ti
 me and unbounded certificates\, as defined by  Balliu\, D’Angelo\, Frai
 gniaud\, and Olivetti [JCSS’18]\, and two other hierarchies that polynom
 ially bound computation and certificate size\, defined by Aldema Tshuva an
 d Oshman [OPODIS’23]\, and by Reiter [PODC’24]. The two definitions fo
 r polynomially bounded local computation differ in the parameter they are 
 polynomial in: Aldema Tshuva and Oshman consider being polynomial in the s
 ize of the graph while Reiter considers each node being polynomial in the 
 size of its local neighborhood.\nI will define the LOCAL model of distribu
 ted computation\, distributed decision tasks in this model and relationshi
 ps between classes of the three hierarchies.\nBased on: https://arxiv.org
 /pdf/2603.29477\n
URL:https://www.tcs.tifr.res.in/web/events/1722
DTSTART;TZID=Asia/Kolkata:20260528T160000
DTEND;TZID=Asia/Kolkata:20260528T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR