2 citations · 2 across the 3 of their papers we have counts for
7 papers
Collision Detection is Instance ptimal Under the Birthday Threshold
Omri Ben-Eliezer, Tomer Grossman, Václav Rozhoň +1
Can structural knowledge about a hash function help accelerate the (black box) detection of collisions in it? This question is fundamental to cryptography theory given the importan…
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…
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…
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…