This Week in Dynamic Optimality

Sleator and Tarjan's dynamic optimality conjecture has been open since the mid 1980s.  The premier data structures thought to be dynamically optimal are the Splay Tree and the Greedy BST.  In this talk I will describe a simple proof that Greedy is $2^{O(\sqrt{\log\log

n})}$-competitive, which is the first non-trivial bound for Greedy. If time permits, I will also survey an approach to resolving special cases of dynamic optimality using forbidden 0-1 matrix theory.