10 citations · 22 across the 14 of their papers we have counts for
5 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…
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 …
A simple and optimal ancestry labeling scheme for trees
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart
We present a ancestry labeling scheme for trees. The problem was first presented by Kannan et al. [STOC 88'] along with a simple solution. Motivat…
Dynamic and Multi-functional Labeling Schemes
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart
We investigate labeling schemes supporting adjacency, ancestry, sibling, and connectivity queries in forests. In the course of more than 20 years, the existence of $\log n + O(\log…
Additive Spanners: A Simple Construction
Mathias Bæk Tejs Knudsen
We consider additive spanners of unweighted undirected graphs. Let be a graph and a subgraph of . The most naïve way to construct an additive -spanner of is the f…