10 citations · 21 across the 11 of their papers we have counts for
16 papers
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…
Constructing Light Spanners Deterministically in Near-Linear Time
Stephen Alstrup, Søren Dahlgaard, Arnold Filtser +2
Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [CW18] improved the state-of-the-art for light spann…
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…
Fast Similarity Sketching
Søren Dahlgaard, Mathias Bæk Tejs Langhede, Jakob Bæk Tejs Houen +1
We consider the problem: Given a universe we want a random function mapping subsets into vectors $S(A…
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…
Fast and Compact Exact Distance Oracle for Planar Graphs
Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen
For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an -space distance oracle which answers…