215 citations · 318 across the 83 of their papers we have counts for
4 papers · 1 filter
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai +1
Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an matrix and will receive column-vectors of size , denoted by $v_1,…
Pattern-avoiding access in binary search trees
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST…
Greedy Is an Almost Optimal Deque
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Patrascu (DHIKP) to accommodate for insertions and deletions. Within this…
Self-Adjusting Binary Search Trees: What Makes Them Tick?
Parinya Chalermsook, Mayank Goswami, Laszlo Kozma +2
Splay trees (Sleator and Tarjan) satisfy the so-called access lemma. Many of the nice properties of splay trees follow from it. What makes self-adjusting binary search trees (BSTs)…