8 citations · 21 across the 23 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.DS2016
DecreaseKeys are Expensive for External Memory Priority Queues
Kasper Eenberg, Kasper Green Larsen, Huacheng Yu
One of the biggest open problems in external memory data structures is the priority queue problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be s…
cs.DS2016★ 8 cited
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication
Omri Weinstein, Huacheng Yu
This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic data structure problems. We introduce a new randomized nondeterministic fou…