6 papers
General Constructions of Permutation-Fair Dice
Tomáš Gavenčiak, Bernhard Haeupler, Václav Rozhoň
Suppose that each of players rolls a different die and the players are ordered by their rolls. Can the dice use disjoint labels such that ties are impossible, while all or…
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…
Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations
Bernhard Haeupler, Marc Kaufmann, Raghu Raman Ravi +1
This paper presents gossip algorithms for aggregation tasks that demonstrate both robustness to adversarial corruptions of any order of magnitude and optimality across a substantia…
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…
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…