O(lg lg n)-competitive Binary Search Trees
John Iacono 
Polytechnic University


Date: Friday October 15, 2004
Time 11-12
Venue: Room 3464, HKUST


Abstract
We present an $O(\lg \lg n)$-competitive online binary search tree,
improving upon the best previous (trivial) competitive ratio of
$O(\lg n)$. This is the first major progress on Sleator and Tarjan's
dynamic optimality conjecture of 1985 that $O(1)$-competitive
binary search trees exist. We will discuss the lower bounds of
Wilber, which our data structure is based on, and the need to
create stronger lower bounds if the $O(\lg \lg n)$-competitive
ratio is to be improved.