BARC/EADS Talk by Thatchaphol Saranurak: Pattern-avoiding Access in Binary Search Trees

Titel

Pattern-avoiding Access in Binary Search Trees.

Abstract

Thatchaphol will talk about a striking conjecture called the dynamic optimality conjecture by Sleator and Tarjan since 1985, which states in high-level that one of the strongest guarantees beyond worst-case analysis is possible for binary search trees (BSTs).

As a stepping stone towards the conjecture, it was open whether there is an (online) BST algorithm whose cost is linear when executing on sequences that avoid (2,3,1)-pattern (i.e. preorder sequences).

In their work, they apply a well-studied forbidden submatrix theory to analyze the cost of the binary search tree algorithm called Greedy. They show that, when a sequence avoids any fixed-size pattern, the cost of Greedy is extremely close to linear (i.e. up to a factor depending on the inverse-Ackermann function).

Bio

Thatchaphol SaranurakThatchaphol Saranurak is PhD student in the Theoretical Computer Science Group (TCS) at School of Computer Science and Communication (CSC), KTH Royal Institute of Technology, Sweden. He currently works on two topics in theoretical computer science. 

  1. Barriers in dynamic graph problems: some dynamic graph problems have resisted many attempts to improve their running time for decades. He investigates those barriers and try to either break them or prove a (conditional) lower bound explaining why it is hard to improve.
  2. Optimal self-adjusting binary search tree algorithms: a famous 30-year-old conjecture called "dynamic optimality conjecture" states that splay tree is an optimal binary search tree algorithm. By formulating related easier questions, solving them, and making connections to many related areas in combinatorics, he is trying to make progress in proving this conjecture.