Arrow Research search

Author name cluster

Mikkel Thorup

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

90 papers
2 author rows

Possible papers

90

STOC Conference 2025 Conference Paper

Solving the Correlation Cluster LP in Sublinear Time

  • Nairen Cao
  • Vincent Cohen-Addad
  • Euiwoong Lee
  • Shi Li 0001
  • David Rasmussen Lolck
  • Alantha Newman
  • Mikkel Thorup
  • Lukas Vogl

Correlation Clustering is a fundamental and widely-studied problem in unsupervised learning and data mining. The input is a graph and the goal is to construct a clustering minimizing the number of inter-cluster edges plus the number of missing intra-cluster edges. Cao, Cohen-Addad, Lee, Li, Newman, and Vogl [STOC 2024] introduced the cluster LP for Correlation Clustering, which they argued captures the problem much more succinctly than previous linear programming formulations. However, the cluster LP has exponential size, with a variable for every possible set of vertices in the input graph. Nevertheless, they showed how to find a feasible solution for the cluster LP in time O ( n poly(1/ε) ) with objective value at most (1+ε) times the value of an optimal solution for the respective Correlation Clustering instance. Furthermore, they showed how to round a solution to the cluster LP, yielding a (1.437+ε)-approximation algorithm for the Correlation Clustering problem. The main technical result of this paper is a new approach to find a feasible solution for the cluster LP with objective value at most (1+ε) of the optimum in time O (2 poly(1/ε) n ), where n is the number of vertices in the graph. We also show how to implement the rounding within the same time bounds, thus achieving a fast (1.437+ε)-approximation algorithm for the Correlation Clustering problem. This bridges the gap between state-of-the-art methods for approximating Correlation Clustering and the recent focus on fast algorithms.

Details

STOC Conference 2024 Conference Paper

Better Coloring of 3-Colorable Graphs

  • Ken-ichi Kawarabayashi
  • Mikkel Thorup
  • Hirotaka Yoneda

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms. In this paper using Blum’s notion of “progress”, we develop a new combinatorial algorithm for the following: Given any 3-colorable graph with minimum degree >√ n , we can, in polynomial time, make progress towards a k -coloring for some k =√ n /· n o (1) . We balance our main result with the best-known semi-definite(SDP) approach which we use for degrees below n 0.605073 . As a result, we show that ( n 0.19747 ) colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of ( n 0.19996 ) by Kawarabayashi and Thorup from 2017.

Details

STOC Conference 2024 Conference Paper

Combinatorial Correlation Clustering

  • Vincent Cohen-Addad
  • David Rasmussen Lolck
  • Marcin Pilipczuk
  • Mikkel Thorup
  • Shuyi Yan
  • Hanwen Zhang 0003

Correlation Clustering is a classic clustering objective arising in numerous machine learning and data mining applications. Given a graph G =( V , E ), the goal is to partition the vertex set into clusters so as to minimize the number of edges between clusters plus the number of edges missing within clusters. The problem is APX-hard and the best known polynomial time approximation factor is 1.73 by Cohen-Addad, Lee, Li, and Newman [FOCS’23]. They use an LP with | V | 1/є Θ(1) variables for some small є. However, due to the practical relevance of correlation clustering, there has also been great interest in getting more efficient sequential and parallel algorithms. The classic combinatorial pivot algorithm of Ailon, Charikar and Newman [JACM’08] provides a 3-approximation in linear time. Like most other algorithms discussed here, this uses randomization. Recently, Behnezhad, Charikar, Ma and Tan [FOCS’22] presented a 3+є-approximate solution for solving problem in a constant number of rounds in the Massively Parallel Computation (MPC) setting. Very recently, Cao, Huang, Su [SODA’24] provided a 2.4-approximation in a polylogarithmic number of rounds in the MPC model and in Õ (| E | 1.5 ) time in the classic sequential setting. They asked whether it is possible to get a better than 3-approximation in near-linear time? We resolve this problem with an efficient combinatorial algorithm providing a drastically better approximation factor. It achieves a ∼ 2−2/13 < 1.847-approximation in sub-linear (Õ(| V |)) sequential time or in sub-linear (Õ(| V |)) space in the streaming setting, and it uses only a constant number of rounds in the MPC model.

Details

SODA Conference 2024 Conference Paper

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

  • Wenyu Jin 0001
  • Xiaorui Sun
  • Mikkel Thorup

We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most c for some c = (log n ) o (1). Previously, the best update time was for any c > 2 and c = O (log n ) [28].

Details

FOCS Conference 2024 Conference Paper

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation

  • Shyam Narayanan
  • Václav Rozhon
  • Jakub Tetek
  • Mikkel Thorup

Suppose we have a memory storing 0s and 1s and we want to estimate the frequency of 1s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a block of $B$ bits at unit cost; not just one bit. If the input consists of uniform blocks: either all 1s or all Os, then sampling a whole block at a time does not reduce the number of samples needed for estimation. On the other hand, if bits are randomly permuted, then getting a block of $B$ bits is as good as getting $B$ indendent bit samples. However, we do not want to make any such assumptions on the input. Instead, our goal is to have an algorithm with instance-dependent performance guarantees which stops sampling blocks as soon as we know that we have a probabilistically reliable estimate. We prove our algorithms to be instance-optimal among algorithms oblivious to the order of the blocks, which we argue is the strongest form of instance optimality we can hope for. We also present similar results for I/O-efficiently estimating mean with both additive and multiplicative error, estimating histograms, quantiles, as well as the empirical cumulative distribution function. We obtain our above results on I/O-efficient sampling by reducing to corresponding problems in the so-called sequential estimation. In this setting, one samples from an unknown distribution until one can provide an estimate with some desired error probability. Sequential estimation has been considered extensively in statistics over the past century. However, the focus has been mostly on parametric estimation, making stringent assumptions on the distribution of the input, and thus not useful for our reduction. In this paper, we make no assumptions on the input distribution (apart from its support being a bounded set). Namely, we provide non-parametric instance-optimal results for several fundamental problems: mean and quantile estimation, as well as learning mixture distributions with respect to $\ell_{\infty}$ and the so-called Kolmogorov-Smirnov distance. All our algorithms are simple, natural, and practical, and some are even known from other contexts, e. g. , from statistics in the parameterized setting. The main technical difficulty is in analyzing them and proving that they are instance optimal.

Details

SODA Conference 2023 Conference Paper

Fully Dynamic Exact Edge Connectivity in Sublinear Time

  • Gramoz Goranci
  • Monika Henzinger
  • Danupon Nanongkai
  • Thatchaphol Saranurak
  • Mikkel Thorup
  • Christian Wulff-Nilsen

Given a simple n -vertex, m -edge graph G undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of G in Õ( n ) worst-case update time and Õ( m 1-1/16 ) amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results answer in the affirmative an open question posed by Thorup [Combinatorica'07].

Details

FOCS Conference 2023 Conference Paper

Locally Uniform Hashing

  • Ioana Oriana Bercea
  • Lorenzo Beretta 0001
  • Jonas Klausen
  • Jakob Bæk Tejs Knudsen
  • Mikkel Thorup

Hashing is a common technique used in data processing, with a strong impact on the time and resources spent on computation. Hashing also affects the applicability of theoretical results that often assume access to (unrealistic) uniform/fully-random hash functions. In this paper, we are concerned with designing hash functions that are practical and come with strong theoretical guarantees on their performance. To this end, we present tornado tabulation hashing, which is simple, fast, and exhibits a certain full, local randomness property that provably makes diverse algorithms perform almost as if (abstract) fully-random hashing was used. For example, this includes classic linear probing, the widely used HyperLogLog algorithm of Flajolet, Fusy, Gandouet, Meunier [AOFA’97] for counting distinct elements, and the one-permutation hashing of Li, Owen, and Zhang [NIPS’12] for large-scale machine learning. We also provide a very efficient solution for the classical problem of obtaining fully-random hashing on a fixed (but unknown to the hash function) set of n keys using $O(n)$ space. As a consequence, we get more efficient implementations of the splitting trick of Dietzfelbinger and Rink [ICALP’09] and the succinct space uniform hashing of Pagh and Pagh [SICOMP’08]. Tornado tabulation hashing is based on a simple method to systematically break dependencies in tabulation-based hashing techniques.

Details

FOCS Conference 2023 Conference Paper

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming

  • Praneeth Kacham
  • Rasmus Pagh
  • Mikkel Thorup
  • David P. Woodruff

We revisit Nisan’s classical pseudorandom generator (PRG) for space-bounded computation (STOC 1990) and its applications in streaming algorithms. We describe a new generator, HashPRG, that can be thought of as a symmetric version of Nisan’s generator over larger alphabets. Our generator allows a trade-off between seed length and the time needed to compute a given block of the generator’s output. HashPRG can be used to obtain derandomizations with much better update time and without sacrificing space for a large number of data stream algorithms, for example: •Andoni’s $F_{p}$ estimation algorithm for constant $p \gt 2$ (ICASSP, 2017) assumes a random oracle, but achieves optimal space and constant update time. Using HashPRG’s time-space trade-off we eliminate the random oracle assumption while preserving the other properties. Previously no time-optimal derandomization was known. Using similar techniques, we give an algorithm for a relaxed version of $\ell_{p}$ sampling in a turnstile stream. Both of our algorithms use $\tilde{O}\left(d^{1-2 / p}\right)$ bits of space and have $O(1)$ update time. •For $0\lt p\lt2$, the $1 \pm \varepsilon$ approximate $F_{p}$ estimation algorithm of Kane et al. , (STOC, 2011) uses an optimal $O\left(\varepsilon^{-2} \log d\right)$ bits of space but has an update time of $O\left(\log ^{2}(1 / \varepsilon) \log \log (1 / \varepsilon)\right)$. Using HashPRG, we show that if $1 / \sqrt{d} \leq \varepsilon \leq 1 / d^{c}$ for an arbitrarily small constant $c \gt 0$, then we can obtain a $1 \pm \varepsilon$ approximate $F_{p}$ estimation algorithm that uses the optimal $O\left(\varepsilon^{-2} \log d\right)$ bits of space and has an update time of $O(\log d)$ in the Word RAM model, which is more than a quadratic improvement in the update time. We obtain similar improvements for entropy estimation. •CountSketch, with the fine-grained error analysis of Minton and Price (SODA, 2014). For derandomization, they suggested a direct application of Nisan’s generator, yielding a logarithmic multiplicative space overhead. With HashPRG we obtain an efficient derandomization yielding the same asymptotic space as when assuming a random oracle. Our ability to obtain a time-efficient derandomization makes crucial use of HashPRG’s symmetry. We also give the first derandomization of a recent private version of CountSketch. For a d-dimensional vector x being updated in a turnstile stream, we show that $\|x\|_{\infty}$ can be estimated up to an additive error of $\varepsilon\|x\|_{2}$ using $O\left(\varepsilon^{-2} \log (1 / \varepsilon) \log d\right)$ bits of space. Additionally, the update time of this algorithm is $O(\log 1 / \varepsilon)$ in the Word RAM model. We show that the space complexity of this algorithm is optimal up to constant factors. However, for vectors x with $\|x\|_{\infty}=\Theta\left(\|x\|_{2}\right)$, we show that the lower bound can be broken by giving an algorithm that uses $O\left(\varepsilon^{-2} \log d\right)$ bits of space which approximates $\|x\|_{\infty}$ up to an additive error of $\varepsilon\|x\|_{2}$. We use our aforementioned derandomization of the CountSketch data structure to obtain this algorithm, and using the time-space trade off of HashPRG, we show that the update time of this algorithm is also $O(\log 1 / \varepsilon)$ in the Word RAM model.

Details

NeurIPS Conference 2022 Conference Paper

Improved Utility Analysis of Private CountSketch

  • Rasmus Pagh
  • Mikkel Thorup

Sketching is an important tool for dealing with high-dimensional vectors that are sparse (or well-approximated by a sparse vector), especially useful in distributed, parallel, and streaming settings. It is known that sketches can be made differentially private by adding noise according to the sensitivity of the sketch, and this has been used in private analytics and federated learning settings. The post-processing property of differential privacy implies that \emph{all} estimates computed from the sketch can be released within the given privacy budget. In this paper we consider the classical CountSketch, made differentially private with the Gaussian mechanism, and give an improved analysis of its estimation error. Perhaps surprisingly, the privacy-utility trade-off is essentially the best one could hope for, independent of the number of repetitions in CountSketch: The error is almost identical to the error from non-private CountSketch plus the noise needed to make the vector private in the original, high-dimensional domain.

PDF Details

FOCS Conference 2021 Conference Paper

Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor

  • Vincent Cohen-Addad
  • Debarati Das 0001
  • Evangelos Kipouridis
  • Nikos Parotsidis
  • Mikkel Thorup

We consider the numerical taxonomy problem of fitting a positive distance function $\mathcal{D}: \binom{S}{2}\rightarrow \mathbb{R}_{> 0}$ by a tree metric. We want a tree $T$ with positive edge weights and including $S$ among the vertices so that their distances in $T$ match those in $\mathcal{D}$. A nice application is in evolutionary biology where the tree $T$ aims to approximate the branching process leading to the observed distances in $\mathcal{D}$ [Cavalli-Sforza and Edwards 1967]. We consider the total error, that is the sum of distance errors over all pairs of points. We present a deterministic polynomial time algorithm minimizing the total error within a constant factor. We can do this both for general trees, and for the special case of ultrametrics with a root having the same distance to all vertices in $S$. The problems are APX-hard, so a constant factor is the best we can hope for in polynomial time. The best previous approximation factor was $O((\log n)(\log\log n)$ ) by Ailon and Charikar [2005] who wrote “Determining whether an $O(1)$ approximation can be obtained is a fascinating question”.

Details

STOC Conference 2020 Conference Paper

Fast hashing with strong concentration bounds

  • Anders Aamand
  • Jakob Bæk Tejs Knudsen
  • Mathias Bæk Tejs Knudsen
  • Peter Michael Reichstein Rasmussen
  • Mikkel Thorup

Previous work on tabulation hashing by Pǎtraşcu and Thorup from STOC’11 on simple tabulation and from SODA’13 on twisted tabulation offered Chernoff-style concentration bounds on hash based sums, e.g., the number of balls/keys hashing to a given bin, but under some quite severe restrictions on the expected values of these sums. The basic idea in tabulation hashing is to view a key as consisting of c = O (1) characters, e.g., a 64-bit key as c =8 characters of 8-bits. The character domain Σ should be small enough that character tables of size |Σ| fit in fast cache. The schemes then use O (1) tables of this size, so the space of tabulation hashing is O (|Σ|). However, the concentration bounds by Pǎtraşcu and Thorup only apply if the expected sums are ≪ |Σ|.

Details

SODA Conference 2020 Conference Paper

Faster Algorithms for Edge Connectivity via Random 2-Out Contractions

  • Mohsen Ghaffari 0001
  • Krzysztof Nowicki 0002
  • Mikkel Thorup

We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each vertex rather than the standard uniform edge sampling. We demonstrate the power of our new approach by obtaining better algorithms for sequential, distributed, and parallel models of computation. Our end results include the following randomized algorithms for computing edge connectivity, with high probability 1: Two sequential algorithms with complexities O ( m log n ) and O ( m + n log 3 n ). These improve on a long line of developments including a celebrated O ( m log 3 n ) algorithm of Karger [STOC'96] and the state of the art O ( m log 2 n (log log n ) 2 ) algorithm of Henzinger et al. [SODA'17]. Moreover, our O ( m + n log 3 n ) algorithm is optimal when m = Ω ( n log 3 n ). An round distributed algorithm, where D denotes the graph diameter. This improves substantially on a recent breakthrough of Daga et al. [STOC'19], which achieved a round complexity of, hence providing the first sublinear distributed algorithm for exactly computing the edge connectivity. The first O (1) round algorithm for the massively parallel computation setting with linear memory per machine.

Details

STOC Conference 2020 Conference Paper

Three-in-a-tree in near linear time

  • Kai-Yuan Lai 0001
  • Hsueh-I Lu
  • Mikkel Thorup

The three-in-a-tree problem is to determine if a simple undirected graph contains an induced subgraph which is a tree connecting three given vertices. Based on a beautiful characterization that is proved in more than twenty pages, Chudnovsky and Seymour [ Combinatorica 2010] gave the previously only known polynomial-time algorithm, running in O ( mn 2 ) time, to solve the three-in-a-tree problem on an n -vertex m -edge graph. Their three-in-a-tree algorithm has become a critical subroutine in several state-of-the-art graph recognition and detection algorithms.

Details

SODA Conference 2019 Conference Paper

Non-empty Bins with Simple Tabulation Hashing

  • Anders Aamand
  • Mikkel Thorup

We consider the hashing of a set X ⊆ U with | X | = m using a simple tabulation hash function h: U → [ n ] = {0, …, n – 1} and analyse the number of non-empty bins, that is, the size of h ( X ). We show that the expected size of h ( X ) matches that with fully random hashing to within low-order terms. We also provide concentration bounds. The number of non-empty bins is a fundamental measure in the balls and bins paradigm, and it is critical in applications such as Bloom filters and Filter hashing. For example, normally Bloom filters are proportioned for a desired low false-positive probability assuming fully random hashing. Our results imply that if we implement the hashing with simple tabulation, we obtain the same low false-positive probability for any possible input.

Details

FOCS Conference 2019 Conference Paper

Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges

  • Jacob Holm
  • Valerie King
  • Mikkel Thorup
  • Or Zamir
  • Uri Zwick

Each vertex of an arbitrary simple graph on n vertices chooses k random incident edges. What is the expected number of edges in the original graph that connect different connected components of the sampled subgraph? We prove that the answer is O(n/k), when k ≥ c log n, for some large enough c. We conjecture that the same holds for smaller values of k, possibly for any k ≥ 2. Such a result is best possible for any k ≥ 2. As an application, we use this sampling result to obtain a one-way communication protocol with private randomness for finding a spanning forest of a graph in which each vertex sends only O (√n log n) bits to a referee.

Details

SODA Conference 2018 Conference Paper

Consistent Hashing with Bounded Loads

  • Vahab Mirrokni
  • Mikkel Thorup
  • Morteza Zadimoghaddam

In dynamic load balancing, we wish to allocate a set of clients (balls) to a set of servers (bins) with the goal of minimizing the maximum load of any server and also minimizing the number of moves after adding or removing a server or a client. We want a hashing-style solution where we given the ID of a client can efficiently find its server in a distributed dynamic environment. In such a dynamic environment, both servers and clients may be added and/or removed from the system in any order. The most popular solutions for such dynamic settings are Consistent Hashing [KLL + 97, SML + 03] or Rendezvous Hashing [TR98]. However, the load balancing of these schemes is no better than a random assignment of clients to servers, so with n of each, we expect many servers to be overloaded with Φ(log n / log log n ) clients. In this paper, we aim to design hashing schemes that achieve any desirable level of load balancing, while minimizing the number of movements under any addition or removal of servers or clients. In particular, we consider a problem with m balls and n bins, and given a user-specified balancing parameter c = 1 + ε > 1, we aim to find a hashing scheme with no load above [ cm/n ], referred to as the capacity of the bins. Our algorithmic starting point is the consistent hashing scheme where current balls and bins are hashed to the unit cycle, and a ball is placed in the first bin succeeding it in clockwise order. In order to cope with given capacity constraints, we apply the idea of linear probing by forwarding the ball on the circle to the first non-full bin. We show that in our hashing scheme when a ball or bin is inserted or deleted, the expected number of balls that have to be moved is within a multiplicative factor of of the optimum for ε ≤ 1 (Theorem 1. 2) and within a factor of the optimum for ε ≥ 1 (Theorem 1. 1). Technically, the latter bound is the most challenging to prove. It implies that for superconstant c, we only pay a negligible cost in extra moves. We also get the same bounds for the simpler problem where, instead of a user specified balancing parameter, we have a fixed bin capacity C for all bins, and define c = 1 + ε = Cn/m.

Details

SODA Conference 2018 Conference Paper

Dynamic Bridge-Finding in Õ (log 2 n ) Amortized Time

  • Jacob Holm
  • Eva Rotenberg
  • Mikkel Thorup

We present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in Õ ((log n ) 2 ) amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any two given vertices, in 𝒪 (log n / log log n ) worst case time. Our bounds match the current best for bounds for deterministic fully-dynamic connectivity up to log log n factors. The previous best dynamic bridge finding was an Õ ((log n) 3 ) amortized time algorithm by Thorup [STOC2000], which was a bittrick-based improvement on the 𝒪 ((log n ) 4 ) amortized time algorithm by Holm et al. [STOC98, JACM2001]. Our approach is based on a different and purely combinatorial improvement of the algorithm of Holm et al. , which by itself gives a new combinatorial Õ ((log n ) 3 ) amortized time algorithm. Combining it with Thorup's bittrick, we get down to the claimed Õ ((log n ) 2 ) amortized time. Essentially the same new trick can be applied to the biconnectivity data structure from [STOC98, JACM2001], improving the amortized update time to Õ ((log n ) 3 ). We also offer improvements in space. We describe a general trick which applies to both of our new algorithms, and to the old ones, to get down to linear space, where the previous best use O ( m + n log n log log n ). Our result yields an improved running time for deciding whether a unique perfect matching exists in a static graph.

Details

STOC Conference 2018 Conference Paper

Fast fencing

  • Mikkel Abrahamsen
  • Anna Adamaszek
  • Karl Bringmann
  • Vincent Cohen-Addad
  • Mehran Mehr
  • Eva Rotenberg
  • Alan Roytman
  • Mikkel Thorup

We consider very natural ”fence enclosure” problems studied by Capoyleas, Rote, and Woeginger and Arkin, Khuller, and Mitchell in the early 90s. Given a set S of n points in the plane, we aim at finding a set of closed curves such that (1) each point is enclosed by a curve and (2) the total length of the curves is minimized. We consider two main variants. In the first variant, we pay a unit cost per curve in addition to the total length of the curves. An equivalent formulation of this version is that we have to enclose n unit disks, paying only the total length of the enclosing curves. In the other variant, we are allowed to use at most k closed curves and pay no cost per curve. For the variant with at most k closed curves,we present an algorithm that is polynomialin both n and k . For the variant with unit cost per curve, or unit disks, we presenta near-linear time algorithm. Capoyleas, Rote, and Woeginger solved the problem with at most k curves in n O ( k ) time. Arkin, Khuller, and Mitchell used this to solve the unit cost per curve version in exponential time. At the time, they conjectured that the problem with k curves is NP-hard for general k . Our polynomial time algorithm refutes this unless P equals NP.

Details

SODA Conference 2018 Conference Paper

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 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 Φ( 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 α, the random permutation needs entropy Ω( n / α ). This contrasts with minwise permutations, where it is known that a 1 + ε approximation only needs Φ(log( n / ε )) entropy. Our negative result for backwards analysis essentially shows that it is as abstract as any analysis based on full randomness.

Details

FOCS Conference 2017 Conference Paper

Fast Similarity Sketching

  • Søren Dahlgaard
  • Mathias Bæk Tejs Knudsen
  • Mikkel Thorup

We consider the Similarity Sketching problem: Given a universe [u] = {0, .. ., u-1} we want a random function S mapping subsets A of [u] into vectors S(A) of size t, such that similarity is preserved. More precisely: Given subsets A, B of [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*J(A, B), where J(A, B) = |A intersect B|/|A union 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 sketches. The seminal t x MinHash algorithm uses t random hash functions h_1, .. ., h_t, and stores (min_{a in A} h_1(A), .. ., min_{a in A} h_t(A)) as the sketch of A. The main drawback of MinHash is, however, its O(t*|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. [NIPS12] introduced 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 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 [ICML14]. However, these densification schemes fail to provide good concentration bounds exactly in the case |A| = O(t), where they are needed. In this paper we present a new sketch which obtains essentially the best of both worlds. That is, a fast O(t log t + |A|) expected running time while getting the same strong concentration bounds as MinHash. Our new sketch can be seen as a mix between sampling with replacement and sampling without replacement. We demonstrate the power of our new sketch by considering popular applications in large-scale classification with linear SVM as introduced by Li et al. [NIPS11] as well as approximate similarity search using the LSH framework of Indyk and Motwani [STOC98]. In particular, for the j_1, j_2-approximate similarity search problem on a collection of n sets we obtain a data-structure with space usage O(n^{1+rho} + sum_{A in C} |A|) and O(n^rho * log n + |Q|) expected time for querying a set Q compared to a O(n^rho * log n * |Q|) expected query time of the classic result of Indyk and Motwani.

Details

NeurIPS Conference 2017 Conference Paper

Practical Hash Functions for Similarity Estimation and Dimensionality Reduction

  • Søren Dahlgaard
  • Mathias 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 assumption that a truly random unit cost hash function is used, without concern for which concrete hash function is employed. The concrete hash function may work fine on sufficiently random input. The question is if it can be trusted in the real world when faced with more structured input. In this paper we focus on two prominent applications of hashing, namely similarity estimation with the one permutation hashing (OPH) scheme of Li et al. [NIPS'12] and feature hashing (FH) of Weinberger et al. [ICML'09], both of which have found numerous applications, i. e. in approximate near-neighbour search with LSH and large-scale classification with SVM. We consider the recent mixed tabulation hash function of Dahlgaard et al. [FOCS'15] which was proved theoretically to perform like a truly random hash function in many applications, including the above OPH. Here we first show improved concentration bounds for FH with truly random hashing and then argue that mixed tabulation performs similar when the input vectors are sparse. Our main contribution, however, is an experimental comparison of different hashing schemes when used inside FH, OPH, and LSH. We find that mixed tabulation hashing is almost as fast as the classic multiply-mod-prime scheme ax+b mod p. Mutiply-mod-prime is guaranteed to work well on sufficiently random data, but we demonstrate that in the above applications, it can lead to bias and poor concentration on both real-world and synthetic data. We also compare with the very popular MurmurHash3, which has no proven guarantees. Mixed tabulation and MurmurHash3 both perform similar to truly random hashing in our experiments. However, mixed tabulation was 40% faster than MurmurHash3, and it has the proven guarantee of good performance on all possible input making it more reliable.

PDF Details

FOCS Conference 2016 Conference Paper

Heavy Hitters via Cluster-Preserving Clustering

  • Kasper Green Larsen
  • Jelani Nelson
  • Huy L. Nguyen 0001
  • Mikkel Thorup

In the turnstile ℓ p heavy hitters problem with parameter ε, one must maintain a high-dimensional vector x ∈ ℝ n subject to updates of the form update (i, Δ) causing the change x i ← x i + Δ, where i ε[n], Δ ∈ ℝ. Upon receiving a query, the goal is to report every "heavy hitter" i ∈ [n] with |x i | ≥ ε ∥x∥ p as part of a list L ⊆ [n] of size O(1/ε p ), i. e. proportional to the maximum possible number of heavy hitters. For any pε(0, 2] the COUNTSKETCH of [CCFC04] solves ℓ p heavy hitters using O(ε -p lg n) words of space with O(lg n) update time, O(n lg n) query time to output L, and whose output after any query is correct with high probability (whp) 1 - 1/poly(n) [JST11, Section 4. 4]. This space bound is optimal even in the strict turnstile model [JST11] in which it is promised that x i ≥ 0 for all i ∈ [n] at all points in the stream, but unfortunately the query time is very slow. To remedy this, the work [CM05] proposed the "dyadic trick" for the COUNTMIN sketch for p = 1 in the strict turnstile model, which to maintain whp correctness achieves suboptimal space O(ε -1 lg 2 n), worse update time O(lg 2 n), but much better query time O(ε -1 poly(lg n)). An extension to all p ∈ (0, 2] appears in [KNPW11, Theorem 1], and can be obtained from [Pag13]. We show that this tradeoff between space and update time versus query time is unnecessary. We provide a new algorithm, EXPANDERSKETCH, which in the most general turnstile model achieves optimal O(ε-plog n) space, O(log n) update time, and fast O(ε-ppoly(log n)) query time, providing correctness whp. In fact, a simpler version of our algorithm for p = 1 in the strict turnstile model answers queries even faster than the "dyadic trick" by roughly a log n factor, dominating it in all regards. Our main innovation is an efficient reduction from the heavy hitters to a clustering problem in which each heavy hitter is encoded as some form of noisy spectral cluster in a much bigger graph, and the goal is to identify every cluster. Since every heavy hitter must be found, correctness requires that every cluster be found. We thus need a "cluster-preserving clustering" algorithm, that partitions the graph into clusters with the promise of not destroying any original cluster. To do this we first apply standard spectral graph partitioning, and then we use some novel combinatorial techniques to modify the cuts obtained so as to make sure that the original clusters are sufficiently preserved. Our cluster-preserving clustering may be of broader interest much beyond heavy hitters.

Details

STOC Conference 2015 Conference Paper

Adjacency Labeling Schemes and Induced-Universal Graphs

  • Stephen Alstrup
  • Haim Kaplan
  • Mikkel Thorup
  • Uri Zwick

We describe a way of assigning labels to the vertices of any undirected graph on up to n vertices, each composed of n/2+O(1) bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an n/2+O(log n) bound of Moon. As a consequence, we obtain an induced-universal graph for n-vertex graphs containing only O(2 n/2 ) vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments and bipartite graphs.

Details

STOC Conference 2015 Conference Paper

Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time

  • Ken-ichi Kawarabayashi
  • Mikkel Thorup

We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. In near-linear time we can also construct the classic cactus representation of all minimum cuts.

Details

STOC Conference 2015 Conference Paper

From Independence to Expansion and Back Again

  • Tobias Christiani
  • Rasmus Pagh
  • Mikkel Thorup

We consider the following fundamental problems: Constructing k-independent hash functions with a space-time tradeoff close to Siegel's lower bound. Constructing representations of unbalanced expander graphs having small size and allowing fast computation of the neighbor function. It is not hard to show that these problems are intimately connected in the sense that a good solution to one of them leads to a good solution to the other one. In this paper we exploit this connection to present efficient, recursive constructions of k-independent hash functions (and hence expanders with a small representation). While the previously most efficient construction (Thorup, FOCS 2013) needed time quasipolynomial in Siegel's lower bound, our time bound is just a logarithmic factor from the lower bound.

Details

FOCS Conference 2015 Conference Paper

Hashing for Statistics over K-Partitions

  • Søren Dahlgaard
  • Mathias Bæk Tejs Knudsen
  • Eva Rotenberg
  • Mikkel Thorup

In this paper we analyze a hash function for k-partitioning a set into bins, obtaining strong concentration bounds for standard algorithms combining statistics from each bin. This generic method was originally introduced by Flajolet and Martin [FOCS'83] in order to save a factor Ω(k) of time per element over k independent samples when estimating the number of distinct elements in a data stream. It was also used in the widely used Hyper Log Log algorithm of Flajolet et al. [AOFA'97] and in large-scale machine learning by Li et al. [NIPS'12] for minwise estimation of set similarity. The main issue of k-partition, is that the contents of different bins may be highly correlated when using popular hash functions. This means that methods of analyzing the marginal distribution for a single bin do not apply. Here we show that a tabulation based hash function, mixed tabulation, does yield strong concentration bounds on the most popular applications of k-partitioning similar to those we would get using a truly random hash function. The analysis is very involved and implies several new results of independent interest for both simple and double tabulation, e. g. A simple and efficient construction for invertible bloom filters and uniform hashing on a given set.

Details

FOCS Conference 2015 Conference Paper

Planar Reachability in Linear Space and Constant Time

  • Jacob Holm
  • Eva Rotenberg
  • Mikkel Thorup

We show how to represent a planar digraph in linear space so that reach ability queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reach ability is thus optimal in both time and space, and has optimal construction time. The previous best solution used O(n log n) space for constant query time [Thorup FOCS'01].

Details

FOCS Conference 2015 Conference Paper

Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8

  • Mikkel Thorup

A random sampling function Sample: U → {0, 1} for a key universe U is a distinguisher with probability. If for any given assignment of values v ( x ) to the keys x ∈ U, including at least one non-zero v ( x ) ≠ 0, the sampled sum Σ{ v ( x ) | x ∈ U ∧ Sample ( x ) = 1} is non-zero with probability at least α. Here the key values may come from any commutative monoid (addition is commutative and associative and zero is neutral). Such distinguishers were introduced by Vazirani [PhD thesis 1986], and Naor and Naor used them for their small bias probability spaces [STOC'90]. Constant probability distinguishers are used for testing in contexts where the key values are not computed directly, yet where the sum is easily computed. A simple example is when we get a stream of key value pairs ( x 1, v 1 ), ( x 2, v 2 ), .. ., ( x n, v n ) where the same key may appear many times. The accumulated value of key x is v ( x ) = Σ{ v 1 | x i = x }. For space reasons, we may not be able to maintain x ( x ) for every key x, but the sampled sum is easily maintained as the single value Σ{ v i | Sample ( x i ) = 1}. Here we show that when dealing with w -bit integers, if a is a uniform odd w -bit integer and t is a uniform w -bit integer, then Sample ( x ) = [ ax mod 2 w ≤ t ] is a distinguisher with probability 1/8. Working with standard units, that is w = 8, 16, 32, 64, we exploit that w -bit multiplication works modulo 2 w, discarding overflow automatically, and then the sampling decision is implemented by the C-code a*x<; =t. Previous such samplers were much less computer-friendly, e. g. The distinguisher of Naor and Naor [STOC'90] was more complicated and involved a 7-independent hash function.

Details

FOCS Conference 2014 Conference Paper

Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search

  • Mihai Patrascu
  • Mikkel Thorup

We present a data structure representing a dynamic set S of w-bit integers on a w-bit word RAM. With |S| = n and w ≥ log n and space O(n), we support the following standard operations in O(log n/log w) time: insert(x) sets S = S + {x}. delete(x) sets S = S {x}. predecessor(x) returns max{y ∈ S | y < x}. rank(x) returns #{y ∈ S | y < x}. select (i) returns y ∈ S with rank (y) = i, if any. Our O(log n/log w) bound is optimal for dynamic rank and select, matching a lower bound of Fredman and Saks [STOC'89]. When the word length is large, our time bound is also optimal for dynamic predecessor, matching a static lower bound of Beame and Fich [STOC'99] whenever log n/log w = O(log w/log log w). Technically, the most interesting aspect of our data structure is that it supports all the above operations in constant time for sets of size n = w O(1). This resolves a main open problem of Ajtai, Komlos, and Fredman [FOCSf83]. Ajtai et al. presented such a data structure in Yaofs abstract cell-probe model with w-bit cells/words, but pointed out that the functions used could not be implemented. As a partial solution to the problem, Fredman and Willard [STOCf90] introduced a fusion node that could handle queries in constant time, but used polynomial time on the updates. We call our small set data structure a dynamic fusion node as it does both queries and updates in constant time.

Details

STOC Conference 2013 Conference Paper

Bottom-k and priority sampling, set similarity and subset sums with minimal independence

  • Mikkel Thorup

We consider bottom-k sampling for a set X, picking a sample S k (X) consisting of the k elements that are smallest according to a given hash function h. With this sample we can estimate the relative size f=|Y|/|X| of any subset Y as |S k (X) intersect Y|/k. A standard application is the estimation of the Jaccard similarity f=|A intersect B|/|A union B| between sets A and B. Given the bottom-k samples from A and B, we construct the bottom-k sample of their union as S k (A union B)=S k (S k (A) union S k (B)), and then the similarity is estimated as |S k (A union B) intersect S k (A) intersect S k (B)|/k.

Details

SODA Conference 2013 Conference Paper

More Compact Oracles for Approximate Distances in Undirected Planar Graphs

  • Ken-ichi Kawarabayashi
  • Christian Sommer 0001
  • Mikkel Thorup

Distance oracles are data structures that provide fast (possibly approximate) answers to shortest-path and distance queries in graphs. The tradeoff between the space requirements and the query time of distance oracles is of particular interest and the main focus of this paper. Unless stated otherwise, we assume all graphs to be planar and undirected. In FOCS 2001 (J. ACM 2004), Thorup introduced approximate distance oracles for planar graphs (concurrent with Klein, SODA 2002). Thorup proved that, for any ε > 0 and for any undirected planar graph G = ( V, E ) on n = | V | nodes, there exists a (1 + ε)-approximate distance oracle using space O ( n ε −1 log n ) such that approximate distance queries can be answered in time O (ε −1 ). In this paper, we aim at reducing the polynomial dependency on ε −1 and log n, getting the first improvement in the query time-space tradeoff. To simplify the statement of our bounds, we define Ō (·) to hide log log n and log(1/ε) factors. We provide the first oracle with a time-space product that is subquadratic in ε −1. We obtain an oracle with space Ō ( n log n ) and query time Ō (ε −1 ). For unweighted graphs we show how the logarithmic dependency on n can be removed. We obtain an oracle with space Ō ( n ) and query time Ō (ε −1 ). This bound also holds for graphs with polylogarithmic average edge length, which may be a quite reasonable assumption, e. g. , for road networks.

Details

FOCS Conference 2013 Conference Paper

Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence

  • Mikkel Thorup

Simple tabulation dates back to Zobrist in 1970 who used it for game playing programs. Keys are viewed as consisting of c characters from some alphabet Φ. We initialize c tables h 0, .. ., h c-1 mapping characters to random hash values. A key x = (x 0, .. ., x c-1 ) is hashed to h 0 [x 0 ]⊕· · ·⊕h c-1 [x c-1 ], where ⊕ denotes bit-wise exclusive-or. The scheme is extremely fast when the character hash tables h i are in cache. Simple tabulation hashing is not even 4-independent, but we show here that if we apply it twice, then we do get high independence. First we hash to some intermediate keys that are 6 times longer than the original keys, and then we hash the intermediate keys to the final hash values. The intermediate keys have d = 6c characters from Φ. We can then view the hash function as a highly unbalanced bipartite graph with keys on one side, each with edges to d output characters on the other side. We show that this graph has nice expansion properties, and from that it follows that if we perform another level of simple tabulation on the intermediate keys, then the composition is a highly independent hash function. More precisely, the independence we get is |Φ|Ω (1/c). In our O-notation, we view both |Φ| and c is going to infinity, but with c much smaller than |Φ|. Our space is O(c|Φ|) and the hash function is evaluated in O(c) time. Siegel [FOCS'89, SICOMP'04] has proved that with this space, if the hash function is evaluated in o(c) time, then the independence can only be o(c), so our evaluation time is best possible for Ω(c) independence-our independence is much higher if c = |Φ| o(1/c). Siegel used O(c) c evaluation time to get the same independence with similar space. Siegel's main focus was c = O(1), but we are exponentially faster when c = ω(1). Applying our scheme recursively, we can increase our independence to |Φ| Ω(1) with o(c logc) evaluation time. Compared with Siegel's scheme this is both faster and higher independence. Siegel states about his scheme that it is “far too slow for any practical application”. Our scheme is trivial to implement, and it does provide realistic implementations of 100-independent hashing for, say, 32-bit and 64-bit keys.

Details

SODA Conference 2013 Conference Paper

Twisted Tabulation Hashing

  • Mihai Patrascu
  • Mikkel Thorup

We introduce a new tabulation-based hashing scheme called “twisted tabulation”. It is essentially as simple and fast as simple tabulation, but has some powerful distributional properties illustrating its promise: (1) If we sample keys with arbitrary probabilities, then with high probability, the number of samples inside any subset is concentrated exponentially. With bounded independence we only get polynomial concentration, and with simple tabulation, we have no good bound even in the basic case of tossing an (unbiased) coin for each key. (2) With classic hash tables such as linear probing and collision-chaining, a window of B operations takes O ( B ) time with high probability, for B = Ω(lg n ). Good amortized performance over any window of size B is equivalent to guaranteed throughput for an on-line system processing a stream via a buffer of size B (e. g. , Internet routers).

Details

FOCS Conference 2012 Conference Paper

A New Infinity of Distance Oracles for Sparse Graphs

  • Mihai Patrascu
  • Liam Roditty
  • Mikkel Thorup

Given a weighted undirected graph, our basic goal is to represent all pairwise distances using much less than quadratic space, such that we can estimate the distance between query vertices in constant time. We will study the inherent trade-off between space of the representation and the stretch (multiplicative approximation disallowing underestimates) of the estimates when the input graph is sparse with m = Õ(n) edges. In this paper, for any fixed positive integers k and ℓ, we obtain stretches = 2k + 1 ± 2/ℓ = 2k + 1 - 2/ℓ, 2k + 1 + 2/ℓ, using space S(α, m) = Õ(m 1+2/(α+1) ). The query time is O(k + ℓ) = O(1). For integer stretches, this coincides with the previous bounds (odd stretches with ℓ = 1 and even stretches with ℓ = 2). The infinity of fractional stretches between consecutive integers are all new (even though ℓ is fixed as a constant independent of the input, the number of integers ℓ is still countably infinite). We will argue that the new fractional points are not just arbitrary, but that they, at least for fixed stretches below 3, provide a complete picture of the inherent trade-off between stretch and space in m. Consider any fixed stretch α 3/2 ) to Ω̃(m 5/3 ), thus matching their upper bound for stretch 2. For space in terms of m, this is the first hardness matching the space of a non-trivial/sub-quadratic distance oracle.

Details

FOCS Conference 2012 Conference Paper

Combinatorial Coloring of 3-Colorable Graphs

  • Ken-ichi Kawarabayashi
  • Mikkel Thorup

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We present a combinatorial algorithm getting down to Õ(n 4/11 ) colors. This is the first combinatorial improvement of Blum's Õ(n 3/8 ) bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite programming approaches. The current best bound is Õ(n 0. 2072 ) colors by Chlamtac from FOCS'07. We now bring it down to Õ(n 0. 2049 ) colors.

Details

STOC Conference 2011 Conference Paper

Don't rush into a union: take time to find your roots

  • Mihai Patrascu
  • Mikkel Thorup

We present a new threshold phenomenon in data structure lower bounds where slightly reduced update times lead to exploding query times. Consider incremental connectivity, letting t u be the time to insert an edge and t q be the query time. For t u = Omega(t q ), the problem is equivalent to the well-understood union-find problem: proc{InsertEdge}(s,t) can be implemented by Union(Find(s), Find(t)). This gives worst-case time t u = t q = O(lg n / lg lg n) and amortized t u = t q = O(α(n)). By contrast, we show that if t u = o(lg n / lg lg n), the query time explodes to t q ≥ n 1-o(1) . In other words, if the data structure doesn't have time to find the roots of each disjoint set (tree) during edge insertion, there is no effective way to organize the information! For amortized complexity, we demonstrate a new inverse-Ackermann type trade-off in the regime t u = o(t q ). A similar lower bound is given for fully dynamic connectivity, where an update time of o(lg n) forces the query time to be n 1-o(1) . This lower bound allows for amortization and Las Vegas randomization, and comes close to the known O(lg n • (lg lg n) O(1) ) upper bound.

Details

FOCS Conference 2011 Conference Paper

The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable

  • Ken-ichi Kawarabayashi
  • Mikkel Thorup

We consider the minimum k-way cut problem for unweighted undirected graphs with a size bound s on the number of cut edges allowed. Thus we seek to remove as few edges as possible so as to split a graph into k components, or report that this requires cutting more than s edges. We show that this problem is fixed-parameter tractable (FPT) with the standard parameterization in terms of the solution size s. More precisely, for s=O(1), we present a quadratic time algorithm. Moreover, we present a much easier linear time algorithm for planar graphs and bounded genus graphs. Our tractability result stands in contrast to known W[1] hardness of related problems. Without the size bound, Downey et al. [2003] proved that the minimum k-way cut problem is W[1] hard with parameter k, and this is even for simple unweighted graphs. Downey et al. asked about the status for planar graphs. We get linear time with fixed parameter k for simple planar graphs since the minimum k-way cut of a planar graph is of size at most 6k. More generally, we get FPT with parameter k for any graph class with bounded average degree. A simple reduction shows that vertex cuts are at least as hard as edge cuts, so the minimum k-way vertex cut is also W[1] hard with parameter k. Marx [2004] proved that finding a minimum k-way vertex cut of size s is also W[1] hard with parameter s. Marx asked about the FPT status with edge cuts, which we prove tractable here. We are not aware of any other cut problem where the vertex version is W[1] hard but the edge version is FPT, e. g. , Marx [2004] proved that the k-terminal cut problem is FPT parameterized by the cut size, both for edge and vertex cuts.

Details

STOC Conference 2011 Conference Paper

The power of simple tabulation hashing

  • Mihai Patrascu
  • Mikkel Thorup

Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting of c characters. We initialize c tables T_1, ..., T_c mapping characters to random hash codes. A key x=(x_1, ..., x_c) is hashed to T_1[x_1] xor ... xor T_c[x_c]. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing.

Details

STOC Conference 2008 Conference Paper

Minimum k-way cuts via deterministic greedy tree packing

  • Mikkel Thorup

We present a simple and fast deterministic algorithm for the minimum k-way cut problem in a capacitated graph, that is, finding a set of edges with minimum total capacity whose removal splits the graph into at least k components. The algorithm packs O(mk 3 log n) trees. Each new tree is a minimal spanning tree with respect to the edge utilizations, and the utilization of an edge is the number of times it has been used in previous spanning trees divided by its capacity. We prove that each minimum k-way cut is crossed at most 2k-2 times by one of the trees. We can enumerate all such cuts in ~O(n 2k ) time, which is hence the running time of our algorithm producing all minimum k-way cuts. The previous fastest deterministic algorithm of Kamidoi et al. [SICOMP'06] took O(n (4+o(1))k ) time, so this is a near-quadratic improvement. Moreover, we essentially match the O(n (2-o(1))k ) running time of the Monto Carlo (no correctness guarantee) randomized algorithm of Karger and Stein [JACM'96].

Details

FOCS Conference 2007 Conference Paper

Planning for Fast Connectivity Updates

  • Mihai Patrascu
  • Mikkel Thorup

Understanding how a single edge deletion can affect the connectivity of a graph amounts to finding the graph bridges. But when faced with d ≫ 1 deletions, can we establish as easily how the connectivity changes? When planning for an emergency, we want to understand the structure of our network ahead of time, and respond swiftly when an emergency actually happens. We describe a linear-space representation of graphs which enables us to determine how a batch of edge updates can impact the graph. Given a set of d edge updates, in time O(d polylg n) we can obtain the number of connected components, the size of each component, and a fast oracle for answering connectivity queries in the updated graph. The initial representation is polynomial-time constructible.

Details

FOCS Conference 2006 Conference Paper

Higher Lower Bounds for Near-Neighbor and Further Rich Problems

  • Mihai Patrascu
  • Mikkel Thorup

We convert cell-probe lower bounds for polynomial space into stronger lower bound for near-linear space. Our technique applies to any lower bound proved through the richness method. For example, it applies to partial match, and to near-neighbor problems, either for randomized exact search, or for deterministic approximate search (which are thought to exhibit the curse of dimensionality). These problems are motivated by search in large data bases, so near-linear space is the most relevant regime. Typically, richness has been used to imply \Omega(d/ lg n) lower bounds for polynomial-space data structures, where d is the number of bits of a query. This is the highest lower bound provable through the classic reduction to communication complexity. However, for space n lg^{O(1)} n, we now obtain bounds of \Omega(d/ lg d). This is a significant improvement for natural values of d, such as lg^{O(1)} n. In the most important case of d = \Theta(lg n), we have the first superconstant lower bound. From a complexity-theoretic perspective, our lower bounds are the highest known for any static data-structure problem, significantly improving on previous records.

Details

STOC Conference 2006 Conference Paper

Time-space trade-offs for predecessor search

  • Mihai Patrascu
  • Mikkel Thorup

We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an explicit problem which breaks this communication complexity barrier. In addition, our bounds give the first separation between polynomial and near linear space. Such a separation is inherently impossible by communication complexity.Using our lower bound technique and new upper bound constructions, we obtain tight bounds for searching predecessors among a static set of integers. Given a set Y of n integers of l bits each, the goal is to efficiently find PREDECESSOR (x) = max (y ∈ Y | y ≤ x). For this purpose, we represent Y on a RAM with word length b using S ≥ nl bits of space. Defining a = lg S/n, we show that the optimal search time is, up to constant factors: min(log b n, lgl-lg n / n, lg(l/a) / lg(a/lg n * lg l/a), lg (l/a) / lg (lg (l/a) / lg (lg n / a)).In external memory (b > l), it follows that the optimal strategy is to use either standard B-trees, or a RAM algorithm ignoring the larger block size. In the important case of b = l = γ lg n, for γ > 1 (i.e. polynomial universes), and near linear space (such as S = n • lg O(1) n), the optimal search time is Θ(lg l). Thus, our lower bound implies the surprising conclusion that van Emde Boas' classic data structure from [FOCS'75] is optimal in this case. Note that for space n 1+ε , a running time of O(lg l / lg lg l) was given by Beame and Fich [STOC'99].

Details

STOC Conference 2005 Conference Paper

Worst-case update times for fully-dynamic all-pairs shortest paths

  • Mikkel Thorup

We present here the first solution to the fully-dynamic all pairs shortest path problem where every update is faster than a recomputation from scratch in Ω( n 3 log ⁄n) time. This is for a directed graph with arbitrary non-negative edge weights. An update inserts or deletes a vertex with all incident edges. After each such vertex update, we update a complete distance matrix in Õ ( n 2.75 ) time.

Details

STOC Conference 2003 Conference Paper

Integer priority queues with decrease key in constant time and the single source shortest paths problem

  • Mikkel Thorup

We consider Fibonacci heap style integer priority queues supporting insert and decrease key operations in constant time. We present a deterministic linear space solution that with n integer keys support delete in O(log log n) time. If the integers are in the range [0,N) , we can also support delete in O(log log N) time.Even for the special case of monotone priority queues, where the minimum has to be non-decreasing, the best previous bounds on delete were O((log n) 1/(3-ε) ) and O((log N) 1/(4-ε) ) . These previous bounds used both randomization and amortization. Our new bounds a deterministic, worst-case, with no restriction to monotonicity, and exponentially faster.As a classical application, for a directed graph with n nodes and m edges with non-negative integer weights, we get single source shortest paths in O(m+n log log n) time, or O(m+n log log C) if C is the maximal edge weight. The later solves an open problem of Ahuja, Mehlhorn, Orlin, and Tarjan from 1990.

Details

STOC Conference 2003 Conference Paper

OPT versus LOAD in dynamic storage allocation

  • Adam L. Buchsbaum
  • Howard J. Karloff
  • Claire Mathieu
  • Nick Reingold
  • Mikkel Thorup

DYNAMIC STORAGE ALLOCATION is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L=LOAD is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT≥LOAD ; previous work showed that OPT≤ 3• LOAD . We continue the study of the relationship between OPT and LOAD , proving that OPT=L+O((h max /L) 1/7 )L , where h max is the maximum job height. Conversely, we prove that for any ε>0 , there exists a c>0 such that for all sufficiently large integers h max , there is a DYNAMIC STORAGE ALLOCATION instance with maximum job height h max , maximum load at most L , and OPT≥ L+c(h max /L) 1/2+ε L , for infinitely many integers L . En route, we construct several new polynomial-time approximation algorithms for DYNAMIC STORAGE ALLOCATION.

Details

STOC Conference 2003 Conference Paper

Space efficient dynamic stabbing with fast queries

  • Mikkel Thorup

In dynamic stabbing, we operate on a dynamic set of intervals. A stabbing query asks for an interval containing a given point. This basic problem encodes problems such as method look-up in object oriented programming languages and classification in IP firewalls. For such application, very fast, say constant, query time is extremely important, small space is very important, and fast updates are good but the least important. Previous solutions traded space and update time for fast queries. We show here that space needs not be sacrificed. We get the same trade-off between update time and query time but using only the space necessary for locating a query point among the interval end-points. All our bounds are optimal or near-optimal.

Details

FOCS Conference 2002 Conference Paper

Equivalence between Priority Queues and Sorting

  • Mikkel Thorup

We present a general deterministic linear space reduction from priority queues to sorting implying that if we can sort up to n keys in S(n) time per key, then there is a priority queue supporting delete and insert in S(n)+O(1) time and find-min in constant time. Conversely, a priority queue can trivially be used for sorting: first insert all keys to be sorted, then extract them in sorted order by repeatedly deleting the minimum. Hence, asymptotically this settles the complexity of priority queues in terms of that of sorting. Besides nailing down the complexity of priority queues to that of sorting, and vice versa, we translate known sorting results into new results on priority queues for integers and strings in different computational models.

Details

FOCS Conference 2002 Conference Paper

Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space

  • Yijie Han
  • Mikkel Thorup

We present a randomized algorithm sorting n integers in O(n/spl radic/(log log n)) expected time and linear space. This improves the previous O(n log log n) bound by Anderson et al. (1995). As an immediate consequence, if the integers are bounded by U, we can sort them in O(n/spl radic/(log log U)) expected time. This is the first improvement over the O (n log log U) bound obtained with van Emde Boas' data structure. At the heart of our construction, is a technical deterministic lemma of independent interest; namely, that we split n integers into subsets of size at most /spl radic/n in linear time and space. This also implies improved bounds for deterministic string sorting and integer sorting without multiplication.

Details

STOC Conference 2001 Conference Paper

Approximate distance oracles

  • Mikkel Thorup
  • Uri Zwick

Let G=(V,E) be an undirected weighted graph with |V|=n and |E|=m. Let k\ge 1 be an integer. We show that G=(V,E) can be preprocessed in O(kmn^{1/k}) expected time, constructing a data structure of size O(kn^{1+1/k}), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k-1, i.e., the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k-1. We show that a 1963 girth conjecture of Erd{\H{o}}s, implies that ω(n^{1+1/k}) space is needed in the worst case for any real stretch strictly smaller than 2k+1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name oracle. Previously, data structures that used only O(n^{1+1/k}) space had a query time of ω(n^{1/k}) and a slightly larger, non-optimal, stretch. Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.}

Details

FOCS Conference 2001 Conference Paper

Compact Oracles for Reachability and Approximate Distances in Planar Digraphs

  • Mikkel Thorup

It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space distance oracle that can answer reachability queries in constant time. The oracle can be distributed as an O(log n) space label for each vertex and then we can determine if one vertex can reach another considering their two labels only. The approach generalizes to approximate distances in weighted planar digraphs where we can then get a (1+/spl epsi/) approximation distance in O(log log /spl Delta/+1//spl epsi/) time where /spl Delta/ is the longest finite distance in the graph and weights are assumed to be non-negative integers. Our scheme can be extended to find and route along the short dipaths. Our technique is based on a novel dipath decomposition of planar digraphs that instead of using the standard separator with O(/spl radic/n) vertices, in effect finds a separator using a constant number of dipaths.

Details

STOC Conference 2001 Conference Paper

Fully-dynamic min-cut

  • Mikkel Thorup

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in \tilde O(\sqrt{n}) time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3 , and even for 3 -edge connectivity, the best update time was O(n^{2/3}) , dating back to FOCS'92.

Details

TCS Journal 1999 Journal Article

Fusion trees can be implemented with AC0 instructions only

  • Arne Andersson
  • Peter Bro Miltersen
  • Mikkel Thorup

Addressing a problem of Fredman and Willard, we implement fusion trees in deterministic linear space using AC0 instructions only. More precisely, we show that a subset of {0, …, 2 w - 1} of size n can be maintained using linear space under insertion, deletion, predecessor, and successor queries, with O( log n log log n ) amortized time per operation on a RAM with word size w, where the only computational instructions allowed on the RAM are functions in AC0. The AC0 instructions used are not all available on today's computers.

Details DOI

I&C Journal 1998 Journal Article

All Structured Programs Have Small Tree Width and Good Register Allocation

  • Mikkel Thorup

The register allocation problem for an imperative program is often modeled as the coloring problem of the interference graph of the control-flow graph of the program. The interference graph of a flow graphGis the intersection graph of some connected subgraphs ofG. These connected subgraphs represent the lives, or life times, of variables, so the coloring problem models that two variables with overlapping life times should be in different registers. For general programs with unrestricted gotos, the interference graph can be any graph, and hence we cannot in general color within a factorO(nε ) from optimality unless NP=P. It is shown that if a graph has tree widthk, we can efficiently color any intersection graph of connected subgraphs within a factor (⌊k/2⌋+1) from optimality. Moreover, it is shown that structured (≡goto-free) programs, including, for example, short circuit evaluations and multiple exits from loops, have tree width at most 6. Thus, for every structured program, we can do register allocation efficiently within a factor 4 from optimality, regardless of how many registers are needed. The bounded tree decomposition may be derived directly from the parsing of a structured program, and it implies that the many techniques for bounded tree width may now be applied in compiler optimization, solving problems in linear time that are NP-hard, or even P-space hard, for general graphs.

Details DOI

FOCS Conference 1998 Conference Paper

Map Graphs in Polynomial Time

  • Mikkel Thorup

Z. Chen et al. (1997, 1998) have introduced a modified notion of planarity, where two faces are considered adjacent if they share at least one point. The corresponding abstract graphs are called map graphs. Chen et al. raised the question of whether map graphs can be recognized in polynomial time. They showed that the decision problem is in NP and presented a polynomial time algorithm for the special case where we allow at most 4 faces to intersect in any point-for only 3 are allowed to intersect in a point, we get the usual planar graphs. Chen et al. conjectured that map graphs can be recognized in polynomial time, and in this paper, their conjecture is settled affirmatively.

Details

FOCS Conference 1997 Conference Paper

Undirected Single Source Shortest Path in Linear Time

  • Mikkel Thorup

The single source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a weighted graph G with a source vertex s, find the shortest path from s to all other vertices in the graph. Since 1959 all theoretical developments in SSSP have been based on Dijkstra's algorithm, visiting the vertices in order of increasing distance from s. Thus, any implementation of Dijkstra's algorithm sorts the vertices according to their distances from s. However, we do not know how to sort in linear time. Here, a deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with integer weights. The algorithm avoids the sorting bottle-neck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.

Details

FOCS Conference 1996 Conference Paper

Static Dictionaries on AC 0 RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient

  • Arne Andersson
  • Peter Bro Miltersen
  • Søren Riis
  • Mikkel Thorup

In this paper we consider solutions to the static dictionary problem on AC/sup 0/ RAMs, i. e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC/sup 0/. Our main result is a tight upper and lower bound of /spl theta/(/spl radic/log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2/sup polylog n/. Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth /spl Omega/(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M. L. Fredman, J. Komlos and E. Szemeredi (1984).

Details

FOCS Conference 1994 Conference Paper

Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract)

  • Martín Farach-Colton
  • Mikkel Thorup

In computational biology one is often interested in finding the concensus between different evolutionary trees for the same set of species. A popular formalizations is the Maximum Agreement Subtree Problem (MAST) defined as follows: given a set A and two rooted trees /spl Tscr//sub 0/ and /spl Tscr//sub 1/ leaf-labeled by the elements of A, find a maximum cardinality subset B of A such that the restrictions of /spl Tscr//sub 0/ and /spl Tscr//sub 1/ to B are topologically isomorphic. Polynomial time solutions exist, but they rely on a dynamic program with /spl Theta/(n/sup 2/) nodes-and /spl Theta/(n/sup 2/) running time. We sparsify this dynamic program and show that MAST is equivalent to Unary Weighted Bipartite Matching (UWBM) modulo an O(nc/sup /spl radic/(log n/) additive overhead. Applying the best bound for UWBM, we get an O(n/sup 1. 5/ log n) algorithm for MAST. From our sparsification follows an O(nc/sup /spl radic/(log n/)) time algorithm for the special case of bounded degrees. Also here the best previous bound was /spl Theta/(n/sup 2/). >

Details
v2026.09.13