ICS Theory Group

ICS 269, Spring 2005: Theory Seminar

27 May 2005:

Nodari Sitchinava

This talk will be a presentation of a paper titled "Dynamic Optimality - Almost [Competitive Online Binary Search Tree" by E. Demaine, D. Harmon, J. Iacono and M. Patrascu. It appeared in FOCS 2004.

Abstract: The paper presents an O(log log 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.