Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
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…
cs.DS2019
Settling the relationship between Wilber's bounds for dynamic optimality
Victor Lecomte, Omri Weinstein
In FOCS 1986, Wilber proposed two combinatorial lower bounds on the operational cost of any binary search tree (BST) for a given access sequence . Both bounds play a c…