# Recent Progress on the Dynamic Optimality Conjecture

## Mayank Goswami, Queens College/CUNY

## Date and time: 2pm, Friday, March 29, 2019

## Place: CUNY Graduate Center, Rm 4419

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, ISAAC 2018) with P. Charlemsook, K. Mehlhorn, L. Kozma and
T. Saranurak.