4 papers
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…
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…