Hardness amplification for dynamic binary search trees

Cites work

O(log log n)-competitive dynamic binary search trees
A counterexample to Comon's conjecture
A counterexample to strong parallel repetition
A new path from Splay to dynamic optimality
An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
Better analysis of binary search tree on decomposable sequences
Dynamic binary search trees: improved lower bounds for the greedy-future Algorithm
Dynamic Optimality—Almost
Greedy is an almost optimal deque
Higher lower bounds for near-neighbor and further rich problems
scientific article; zbMATH DE number 1670671 (Why is no real title available?)
scientific article; zbMATH DE number 5764839 (Why is no real title available?)
scientific article; zbMATH DE number 7651167 (Why is no real title available?)
scientific article; zbMATH DE number 7651207 (Why is no real title available?)
scientific article; zbMATH DE number 7758335 (Why is no real title available?)
Improved pattern-avoidance bounds for Greedy BSTs via matrix decomposition
In pursuit of the dynamic optimality conjecture
Log-rank and lifting for AND-functions
Lower Bounds for Accessing Binary Search Trees with Rotations
On the deque conjecture for the splay algorithm
On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
On the sequential access theorem and deque conjecture for splay trees
On Yao's XOR-lemma
Pattern-avoiding access in binary search trees
Self-adjusting binary search trees
Self-Organizing Binary Search Trees
Separation of the monotone NC hierarchy
Smooth heaps and a dual view of self-adjusting data structures
Sorting pattern-avoiding permutations via 0-1 matrices forbidding product patterns
Strong direct product theorems for quantum communication and query complexity
Super-logarithmic depth lower bounds via the direct sum in communication complexity
The geometry of binary search trees
The geometry of tree-based sorting
Upper bounds for maximally greedy binary search trees

This page was built for publication: Hardness amplification for dynamic binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7260661)