51²è¹Ý

Dear All,

The Department of Computer Science invites you to a seminar on "The Group Access Bounds for Binary Search Trees"

Abstract: In Binary Search Trees (BSTs), the access lemma (Sleator and Tarjan, JACM 1985) is a property such that if a BST algorithm satisfies the access lemma, then as a consequence, it satisfies many other BST properties, such as Balance Theorem, Static optimality, Static finger, Working set, etc. However, there are many BST properties that are not known to be derived via the access lemma, such as dynamic finger, o(log n)-competitiveness, k-finger, etc. To overcome this, we introduce the group access bounds that generalize the access lemma and imply properties that are far stronger than those implied by the classical access lemma. Using the group access bounds, we give improved results for k-finger,  o(log n)-competitiveness, unified bound, and unified bound with a time window.

Furthermore, we prove the simulation theorem: For every group access tree, there is an online BST algorithm that is O(1)-competitive with its group access bound. In particular, any new group access bound will automatically imply a new BST algorithm achieving the same bound. Thereby, we obtain an improved k-finger bound (reference tree is an almost complete binary tree), an improved unified bound with a time window k, and matching the best-known bound for Unified bound in the BST model. Since any dynamically optimal BST must achieve the group access bounds, we believe our results provide a new direction towards proving o(log n)-competitiveness of Splay tree and Greedy, two prime candidates for the dynamic optimality conjecture.

About the Speaker:  Akash Pareek is a Postdoctoral Researcher in the Department of Computer Science at Université libre de Bruxelles, where he is hosted by Prof. John Iacono. Previously, he was a Walmart and KIAC Postdoctoral Fellow at IISc Bangalore, working with Prof. Arindam Khan. He earned his Ph.D. in Computer Science from IIT Gandhinagar under the supervision of Prof. Manoj Gupta. His research interests lie in theoretical computer science, with a focus on data structures, online algorithms, clustering, and algorithms with predictions.

We look forward to your active participation.