4 citations · 23 across the 22 of their papers we have counts for
4 papers · 1 filter
Hashing for statistics over k-partitions
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg +1
In this paper we analyze a hash function for -partitioning a set into bins, obtaining strong concentration bounds for standard algorithms combining statistics from each bin. Thi…
Planar Reachability in Linear Space and Constant Time
Jacob Holm, Eva Rotenberg, Mikkel Thorup
We show how to represent a planar digraph in linear space so that distance queries can be answered in constant time. The data structure can be constructed in linear time. This repr…
Faster Fully-Dynamic Minimum Spanning Forest
Jacob Holm, Eva Rotenberg, Christian Wulff-Nilsen
We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in amortized time per operat…
The Power of Two Choices with Simple Tabulation
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg +1
The power of two choices is a classic paradigm for load balancing when assigning balls to bins. When placing a ball, we pick two bins according to two hash functions …