Hardness Amplification for Dynamic Binary Search Trees

Shunhua Jiang, Victor Lecomte, Omri Weinstein +1

We prove direct-sum theorems for Wilber's two lower bounds [Wilber, FOCS'86] on the cost of access sequences in the binary search tree (BST) model. These bounds are central to the…