A binary search tree (BST) is dynamically optimal if it processes any search sequence X in time within a constant factor of the offline optimum. Sleator and Tarjan (JACM 1985) famously conjectured that the Splay Tree achieves dynamic optimality—this is the dynamic optimality conjecture. Despite its significance, progress has been limited. More recently, Demaine et al. (SODA 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.

Short Bio:

Manoj Gupta is an Associate Professor at IIT Gandhinagar. He received his Ph.D. from IIT Delhi. His research interests are Dynamic, Fault-tolerant, and Graph Algorithms.