6 papers
Heaps and Their Working Sets
Bernhard Haeupler, Richard Hladík, Václav Rozhoň +1
We construct a heap with strong beyond-worst-case performance guarantees and explore the analysis of such heaps. First, we unify existing notions of the working-set bound for heaps…
Splay trees are almost dynamically optimal
Petr Chmel, Bernhard Haeupler, Richard Hladík +5
Sleator and Tarjan [JACM, 1985] conjectured that splay trees are dynamically optimal -- that on every access sequence, they perform within a constant factor of the optimal offline…
Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
Bernhard Haeupler, Richard Hladík, Shengzhe Wang +1
This paper significantly strengthens directed low-diameter decompositions in several ways. We define and give the first results for separated low-diameter decompositions in directe…
Bidirectional Dijkstra's Algorithm is Instance-Optimal
Bernhard Haeupler, Richard Hladík, Vaclav Rozhon +2
Although Dijkstra's algorithm has near-optimal time complexity for the problem of finding a shortest path from a given vertex to a given vertex , in practice other algorithm…
Smooth Sensitivity Revisited: Towards Optimality
Richard Hladík, Jakub Tětek
Smooth sensitivity is one of the most commonly used techniques for designing practical differentially private mechanisms. In this approach, one computes the smooth sensitivity of a…
Near-Universally-Optimal Differentially Private Minimum Spanning Trees
Richard Hladík, Jakub Tětek
Devising mechanisms with good beyond-worst-case input-dependent performance has been an important focus of differential privacy, with techniques such as smooth sensitivity, propose…