BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1548
DTSTAMP:20250703T044924Z
SUMMARY:Dynamic optimality conjecture and related open problems
DESCRIPTION:Speaker: Manoj Gupta (IIT Gandhinagar)\n\nAbstract: \nA binary 
 search tree (BST) is dynamically optimal if it processes any search sequen
 ce X in time within a constant factor of the offline optimum. Sleator and 
 Tarjan (JACM 1985) famously conjectured that the Splay Tree achieves dynam
 ic optimality—this is the dynamic optimality conjecture. Despite its sig
 nificance\, progress has been limited. More recently\, Demaine et al. (SOD
 A 2009) proposed another BST\, GREEDY\, also conjectured to be dynamically
  optimal. The central goal remains: prove that either Splay Tree or GREEDY
  achieves dynamic optimality. In this talk\, we'll explore recent advances
  and highlight key open problems.\nShort Bio:\nManoj Gupta is an Associate
  Professor at IIT Gandhinagar. He received his Ph.D. from IIT Delhi. His r
 esearch interests are Dynamic\, Fault-tolerant\, and Graph Algorithms.\n
URL:https://www.tcs.tifr.res.in/web/events/1548
DTSTART;TZID=Asia/Kolkata:20250722T160000
DTEND;TZID=Asia/Kolkata:20250722T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR