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