10 citations · 22 across the 14 of their papers we have counts for
19 papers
Fast hashing with Strong Concentration Bounds
Anders Aamand, Jakob B. T. Knudsen, Mathias B. T. Knudsen +2
Previous work on tabulation hashing by Patrascu and Thorup from STOC'11 on simple tabulation and from SODA'13 on twisted tabulation offered Chernoff-style concentration bounds on h…
Power of Choices with Simple Tabulation
Anders Aamand, Mathias Bæk Tejs Knudsen, Mikkel Thorup
Suppose that we are to place balls into bins sequentially using the -choice paradigm: For each ball we are given a choice of bins, according to hash functions $h…
Practical Hash Functions for Similarity Estimation and Dimensionality Reduction
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Mikkel Thorup
Hashing is a basic tool for dimensionality reduction employed in several aspects of machine learning. However, the perfomance analysis is often carried out under the abstract assum…
Linear Hashing is Awesome
Mathias Bæk Tejs Knudsen
We consider the hash function where are chosen uniformly at random from . We prove that when we use in hashing wi…
The Entropy of Backwards Analysis
Mathias Bæk Tejs Knudsen, Mikkel Thorup
Backwards analysis, first popularized by Seidel, is often the simplest most elegant way of analyzing a randomized algorithm. It applies to incremental algorithms where elements are…
Additive Spanners and Distance Oracles in Quadratic Time
Mathias Bæk Tejs Knudsen
Let be an unweighted, undirected graph. An additive -spanner of is a subgraph that approximates all distances between pairs of nodes up to an additive error of ,…
New Subquadratic Approximation Algorithms for the Girth
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel
We consider the problem of approximating the girth, , of an unweighted and undirected graph with nodes and edges. A seminal result of Itai and Rodeh [SICOMP'78…
Maximal Unbordered Factors of Random Strings
Patrick Hagge Cording, Travis Gagie, Mathias Bæk Tejs Knudsen +1
A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border other than itself. Loptev, Kucherov, an…
Finding Even Cycles Faster via Capped k-Walks
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Morten Stöckel
In this paper, we consider the problem of finding a cycle of length (a ) in an undirected graph with nodes and edges for constant . A classic result…
Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
Mikkel Abrahamsen, Stephen Alstrup, Jacob Holm +2
A graph is an induced universal graph for a family of graphs if every graph in is a vertex-induced subgraph of . For the family of all undirected graphs on verti…
Sublinear Distance Labeling
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen +1
A distance labeling scheme labels the nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the…
Longest Common Extensions in Sublinear Space
Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen +2
The longest common extension problem (LCE problem) is to construct a data structure for an input string of length that supports LCE queries. Such a query returns the…
Optimal induced universal graphs and adjacency labeling for trees
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen
We show that there exists a graph with nodes, where any forest of nodes is a node-induced subgraph of . Furthermore, for constant arboricity , the result impli…
Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence
Mathias Bæk Tejs Knudsen, Morten Stöckel
Randomized algorithms and data structures are often analyzed under the assumption of access to a perfect source of randomness. The most fundamental metric used to measure how "rand…
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…