Showing 2026Show all
3 papers · 1 filter
math.CO2026
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…
cs.DS2026
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…
cs.DS2026
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…