6 papers
Fast and Simple Sorting Using Partial Information
Bernhard Haeupler, Richard HladÃk, John Iacono +3
We consider the problem of sorting items, given the outcomes of pre-existing comparisons. We present a simple and natural deterministic algorithm that runs in $O(m + \log T…
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…
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Bernhard Haeupler, Richard HladÃk, Václav RozhoÅ +2
In this paper we prove that Dijkstra's shortest-path algorithm, if implemented with a sufficiently efficient heap, is universally optimal in its running time, and with suitable sma…
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
Shyam Narayanan, Václav RozhoÅ, Jakub TÄtek +1
Suppose we have a memory storing s and s and we want to estimate the frequency of s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a bloc…
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…