MKMathias Bæk Tejs Knudsen
Mathias Bæk Tejs Knudsen
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Interests
Mathias Bæk Tejs Knudsen has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Mikkel Thorup
BARC University of Copenhagen
2 shared publications - Jakob Bæk Tejs Houen
University of Copenhagen
1 shared publication - Patrick Hagge Cording1 shared publication
- Søren Dahlgaard
University of Copenhagen
1 shared publication - Tomasz Kociumaka
Saarland Informatics Campus, Max Planck Institute for Informatics, Saarbrücken, Germany
1 shared publication - Travis Gagie
Faculty of Computer Science, Dalhousie University, Halifax, Canada
1 shared publication
Latest Publications
- Open Access
Fast Similarity Sketching
We consider the $\textit{Similarity Sketching}$ problem: Given a universe $[u] = \{0,\ldots, u-1\}$ we want a random function $S$ mapping subsets $A\subseteq [u]$ into vectors $S(A)$ of size $t$, such that similarity is preserved. More precisely: Given sets $A,B\subseteq [u]$, define $X_i = [S(A)[i] = S(B)[i]]$ and $X = \sum_{i\in [t]} X_i$. We want to have $E[X] = t\cdot J(A,B)$, where $J(A,B) = |A\cap B|/|A\cup B|$ and furthermore to have strong concentration guarantees (i.e. Chernoff-style bounds) for $X$. This is a fundamental problem which has found numerous applications in data mining, large-scale classification, computer vision, similarity search, etc. via the classic MinHash algorithm. The vectors $S(A)$ are also called $\textit{sketches}$. The seminal $t\times\textit{MinHash}$ algorithm uses $t$ random hash functions $h_1,\ldots, h_t$, and stores $\left ( \min_{a\in A} h_1(A),\ldots, \min_{a\in A} h_t(A) \right )$ as the sketch of $A$. The main drawback of MinHash is, however, its $O(t\cdot |A|)$ running time, and finding a sketch with similar properties and faster running time has been the subject of several papers. Addressing this, Li et al.~[NIPS'12] introduced $\textit{one permutation hashing (OPH)}$, which creates a sketch of size $t$ in $O(t + |A|)$ time, but with the drawback that possibly some of the $t$ entries are ``empty'' when $|A| = O(t)$. One could argue that sketching is not necessary in this case, however the desire in most applications is to have $\textit{one}$ sketching procedure that works for sets of all sizes. Therefore, filling out these empty entries is the subject of several follow-up papers initiated by Shrivastava and Li~[ICML'14]. However, these ``densification'' schemes fail to provide good concentration bounds exactly in the case $|A| = O(t)$, where they are needed. (continued...)Open AccessFast Similarity Sketching
We consider the $\textit{Similarity Sketching}$ problem: Given a universe $[u] = \{0,\ldots, u-1\}$ we want a random function $S$ mapping subsets $A\subseteq [u]$ into vectors $S(A)$ of size $t$, such that similarity is preserved. More precisely: Given sets $A,B\subseteq [u]$, define $X_i = [S(A)[i] = S(B)[i]]$ and $X = \sum_{i\in [t]} X_i$. We want to have $E[X] = t\cdot J(A,B)$, where $J(A,B) = |A\cap B|/|A\cup B|$ and furthermore to have strong concentration guarantees (i.e. Chernoff-style bounds) for $X$. This is a fundamental problem which has found numerous applications in data mining, large-scale classification, computer vision, similarity search, etc. via the classic MinHash algorithm. The vectors $S(A)$ are also called $\textit{sketches}$. The seminal $t\times\textit{MinHash}$ algorithm uses $t$ random hash functions $h_1,\ldots, h_t$, and stores $\left ( \min_{a\in A} h_1(A),\ldots, \min_{a\in A} h_t(A) \right )$ as the sketch of $A$. The main drawback of MinHash is, however, its $O(t\cdot |A|)$ running time, and finding a sketch with similar properties and faster running time has been the subject of several papers. Addressing this, Li et al.~[NIPS'12] introduced $\textit{one permutation hashing (OPH)}$, which creates a sketch of size $t$ in $O(t + |A|)$ time, but with the drawback that possibly some of the $t$ entries are ``empty'' when $|A| = O(t)$. One could argue that sketching is not necessary in this case, however the desire in most applications is to have $\textit{one}$ sketching procedure that works for sets of all sizes. Therefore, filling out these empty entries is the subject of several follow-up papers initiated by Shrivastava and Li~[ICML'14]. However, these ``densification'' schemes fail to provide good concentration bounds exactly in the case $|A| = O(t)$, where they are needed. (continued...) - Open Access
Maximal Unbordered Factors of Random Strings
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, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length $n$ from a fixed non-unary alphabet uniformly at random, then the expected maximum length of its unbordered factors is $n - O(1)$. We confirm this conjecture by proving that the expected value is, in fact, ${n - \Theta(\sigma^{-1})}$, where $\sigma$ is the size of the alphabet. This immediately implies that we can find such a maximal unbordered factor in linear time on average. However, we go further and show that the optimum average-case running time is in $\Omega (\sqrt{n}) \cap O (\sqrt{n \log_\sigma n})$ due to analogous bounds by Czumaj and G\k{a}sieniec [CPM 2000] for the problem of computing the shortest period of a uniformly random string.Open AccessMaximal Unbordered Factors of Random Strings
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, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length $n$ from a fixed non-unary alphabet uniformly at random, then the expected maximum length of its unbordered factors is $n - O(1)$. We confirm this conjecture by proving that the expected value is, in fact, ${n - \Theta(\sigma^{-1})}$, where $\sigma$ is the size of the alphabet. This immediately implies that we can find such a maximal unbordered factor in linear time on average. However, we go further and show that the optimum average-case running time is in $\Omega (\sqrt{n}) \cap O (\sqrt{n \log_\sigma n})$ due to analogous bounds by Czumaj and G\k{a}sieniec [CPM 2000] for the problem of computing the shortest period of a uniformly random string. - Open Access
Linear Hashing is Awesome
We consider the hash function $h(x) = ((ax+b) \bmod p) \bmod n$ where $a,b$ are chosen uniformly at random from $\{0,1,\ldots,p-1\}$. We prove that when we use $h(x)$ in hashing with chaining to insert $n$ elements into a table of size $n$ the expected length of the longest chain is $\tilde{O}\!\left(n^{1/3}\right)$. The proof also generalises to give the same bound when we use the multiply-shift hash function by Dietzfelbinger et al. [Journal of Algorithms 1997].Open AccessLinear Hashing is Awesome
We consider the hash function $h(x) = ((ax+b) \bmod p) \bmod n$ where $a,b$ are chosen uniformly at random from $\{0,1,\ldots,p-1\}$. We prove that when we use $h(x)$ in hashing with chaining to insert $n$ elements into a table of size $n$ the expected length of the longest chain is $\tilde{O}\!\left(n^{1/3}\right)$. The proof also generalises to give the same bound when we use the multiply-shift hash function by Dietzfelbinger et al. [Journal of Algorithms 1997]. - Open Access
The Entropy of Backwards Analysis
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 added incrementally, following some random permutation, e.g., incremental Delauney triangulation of a pointset, where points are added one by one, and where we always maintain the Delauney triangulation of the points added thus far. For backwards analysis, we think of the permutation as generated backwards, implying that the $i$th point in the permutation is picked uniformly at random from the $i$ points not picked yet in the backwards direction. Backwards analysis has also been applied elegantly by Chan to the randomized linear time minimum spanning tree algorithm of Karger, Klein, and Tarjan. The question considered in this paper is how much randomness we need in order to trust the expected bounds obtained using backwards analysis, exactly and approximately. For the exact case, it turns out that a random permutation works if and only if it is minwise, that is, for any given subset, each element has the same chance of being first. Minwise permutations are known to have $\Theta(n)$ entropy, and this is then also what we need for exact backwards analysis. However, when it comes to approximation, the two concepts diverge dramatically. To get backwards analysis to hold within a factor $\alpha$, the random permutation needs entropy $\Omega(n/\alpha)$. This contrasts with minwise permutations, where it is known that a $1+\varepsilon$ approximation only needs $\Theta(\log (n/\varepsilon))$ entropy. Our negative result for backwards analysis essentially shows that it is as abstract as any analysis based on full randomness.Open AccessThe Entropy of Backwards Analysis
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 added incrementally, following some random permutation, e.g., incremental Delauney triangulation of a pointset, where points are added one by one, and where we always maintain the Delauney triangulation of the points added thus far. For backwards analysis, we think of the permutation as generated backwards, implying that the $i$th point in the permutation is picked uniformly at random from the $i$ points not picked yet in the backwards direction. Backwards analysis has also been applied elegantly by Chan to the randomized linear time minimum spanning tree algorithm of Karger, Klein, and Tarjan. The question considered in this paper is how much randomness we need in order to trust the expected bounds obtained using backwards analysis, exactly and approximately. For the exact case, it turns out that a random permutation works if and only if it is minwise, that is, for any given subset, each element has the same chance of being first. Minwise permutations are known to have $\Theta(n)$ entropy, and this is then also what we need for exact backwards analysis. However, when it comes to approximation, the two concepts diverge dramatically. To get backwards analysis to hold within a factor $\alpha$, the random permutation needs entropy $\Omega(n/\alpha)$. This contrasts with minwise permutations, where it is known that a $1+\varepsilon$ approximation only needs $\Theta(\log (n/\varepsilon))$ entropy. Our negative result for backwards analysis essentially shows that it is as abstract as any analysis based on full randomness. - Open Access
Additive Spanners and Distance Oracles in Quadratic Time
Let $G$ be an unweighted, undirected graph. An additive $k$-spanner of $G$ is a subgraph $H$ that approximates all distances between pairs of nodes up to an additive error of $+k$, that is, it satisfies $d_H(u,v) \le d_G(u,v)+k$ for all nodes $u,v$, where $d$ is the shortest path distance. We give a deterministic algorithm that constructs an additive $O\!\left(1\right)$-spanner with $O\!\left(n^{4/3}\right)$ edges in $O\!\left(n^2\right)$ time. This should be compared with the randomized Monte Carlo algorithm by Woodruff [ICALP 2010] giving an additive $6$-spanner with $O\!\left(n^{4/3}\log^3 n\right)$ edges in expected time $O\!\left(n^2\log^2 n\right)$. An $(\alpha,\beta)$-approximate distance oracle for $G$ is a data structure that supports the following distance queries between pairs of nodes in $G$. Given two nodes $u$, $v$ it can in constant time compute a distance estimate $\tilde{d}$ that satisfies $d \le \tilde{d} \le \alpha d + \beta$ where $d$ is the distance between $u$ and $v$ in $G$. Sommer [ICALP 2016] gave a randomized Monte Carlo $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\text{poly} \log n\right)$ in expected time $O\!\left(n^2\text{poly} \log n\right)$. As an application of the additive $O(1)$-spanner we improve the construction by Sommer [ICALP 2016] and give a Las Vegas $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\right)$ in time $O\!\left(n^2\right)$. This also implies an algorithm that in $O\!\left(n^2\right)$ gives approximate distance for all pairs of nodes in $G$ improving on the $O\!\left(n^2 \log n\right)$ algorithm by Baswana and Kavitha [SICOMP 2010].Open AccessAdditive Spanners and Distance Oracles in Quadratic Time
Let $G$ be an unweighted, undirected graph. An additive $k$-spanner of $G$ is a subgraph $H$ that approximates all distances between pairs of nodes up to an additive error of $+k$, that is, it satisfies $d_H(u,v) \le d_G(u,v)+k$ for all nodes $u,v$, where $d$ is the shortest path distance. We give a deterministic algorithm that constructs an additive $O\!\left(1\right)$-spanner with $O\!\left(n^{4/3}\right)$ edges in $O\!\left(n^2\right)$ time. This should be compared with the randomized Monte Carlo algorithm by Woodruff [ICALP 2010] giving an additive $6$-spanner with $O\!\left(n^{4/3}\log^3 n\right)$ edges in expected time $O\!\left(n^2\log^2 n\right)$. An $(\alpha,\beta)$-approximate distance oracle for $G$ is a data structure that supports the following distance queries between pairs of nodes in $G$. Given two nodes $u$, $v$ it can in constant time compute a distance estimate $\tilde{d}$ that satisfies $d \le \tilde{d} \le \alpha d + \beta$ where $d$ is the distance between $u$ and $v$ in $G$. Sommer [ICALP 2016] gave a randomized Monte Carlo $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\text{poly} \log n\right)$ in expected time $O\!\left(n^2\text{poly} \log n\right)$. As an application of the additive $O(1)$-spanner we improve the construction by Sommer [ICALP 2016] and give a Las Vegas $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\right)$ in time $O\!\left(n^2\right)$. This also implies an algorithm that in $O\!\left(n^2\right)$ gives approximate distance for all pairs of nodes in $G$ improving on the $O\!\left(n^2 \log n\right)$ algorithm by Baswana and Kavitha [SICOMP 2010].