10 citations · 14 across the 5 of their papers we have counts for
7 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…
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…
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…