Time: 11am-12pm
Place: CS 220 (new CS building, seminar room, 2nd floor)

Guest speaker: Mayank Goswami

Title: On Clairvoyance in Binary Search Trees: Recent Progress on the Dynamic Optimality Conjecture

Abstract: The dynamic optimality conjecture is the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i.e., one that is constant factor competitive with any BST on any input sequence, even with one that knows the entire sequence in advance. The two main candidates for dynamic optimality are splay trees [Sleator and Tarjan, 1985] and GREEDY [Lucas, 1988; Munro, 2000; Demaine et al. 2009]. Despite BSTs being among the simplest data structures in computer science and despite extensive effort over the past three decades, the conjecture remains elusive. Dynamic optimality is achieved for almost all sequences, as the majority of them are hard and have optimum cost \theta(n log n), achievable by any balanced BST. Thus the missing step towards the conjecture is understanding “easy” access sequences.

One prominent example is the traversal conjecture [Sleator and Tarjan, 1985] which states that preorder sequences are accessed in linear time by splay trees; no online BST was known to satisfy this conjecture until now.

In this talk I will survey the literature on dynamic optimality and present a proof of the traversal conjecture for GREEDY. I will also present a proof that Splay trees are not black magic, and end with some promising open problems. The talk will be accessible to anyone who knows what a binary tree is.

This talk is based on joint work (appearing in WADS, ESA and FOCS 2015) with P. Charlemsook, K. Mehlhorn, L. Kozma and T. Saranurak from the Max-Planck Institute for Informatics. 

Short bio: Mayank Goswami is a postdoctoral scholar with the Algorithms and Complexity Group at Max-Planck Institute for Informatics, Saarbruecken, Germany. His MPII host is Prof. Kurt Mehlhorn. He is an SBU (AMS) alumni. He obtained his PhD in 2013 working with Professors Joseph S.B. Mitchell and Xianfeng Gu. He has a BMath (Honors) in Mathematics from Indian Statistical Institute, Bangalore, India. He is an Algorithms Reading Group veteran. Homepage: http://people.mpi-inf.mpg.de/~gmayank/