Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [Mach. Learn. '04]. The input is an unweighted, undirected graph. The problem is to cluster the vertices so as to minimize the number of edges between vertices in different clusters and missing edges between vertices inside the same cluster. This problem has a wide application in data mining and machine learning. We introduce a general framework that transforms existing static correlation clustering algorithms into fully-dynamic ones that work against an adaptive adversary. We show how to apply our framework to known efficient correlation clustering algorithms, starting from the classic 3-approximate Pivot algorithm from Ailon, Charikar and Newman [JACM'08]. Applied to the most recent sublinear $1.485$-approximation algorithm from Cao, Cohen-Addad, Lee, Li, Lolck, Newman, Thorup, Vogl, Yan and Zhang [STOC'25], we get a $1.485$-approximation fully-dynamic algorithm that works with worst-case constant update time. The original static algorithm gets its approximation factor with constant probability, and we get the same against an adaptive adversary in the sense that for any given update step, not known to our algorithm, our solution is a $1.485$-approximation with constant probability when we reach this update. Most of previous dynamic algorithms, including the celebrated result from Behnezhad, Charikar, Ma and Tan [FOCS'19], had approximation factors around $3$ in expectation, and they could only handle an oblivious adversary. A recent algorithm by Braverman, Dharangutte, Pai, Shah, and Wang [AISTATS'25] could handle an adaptive adversary, but it has a large unspecified constant approximation ratio. This contrasts with our general transformation, which works with all the best approximation factors known for the static case.

We present a randomized Õ(n^{3.5})-time algorithm for computing optimal energetic paths for an electric car between all pairs of vertices in an n-vertex directed graph with positive and negative costs, or gains, which are defined to be the negatives of the costs. The optimal energetic paths are finite and well-defined even if the graph contains negative-cost, or equivalently, positive-gain, cycles. This makes the problem much more challenging than standard shortest paths problems. More specifically, for every two vertices s and t in the graph, the algorithm computes α_B(s,t), the maximum amount of charge the car can reach t with, if it starts at s with full battery, i.e., with charge B, where B is the capacity of the battery. The algorithm also outputs a concise description of the optimal energetic paths that achieve these values. In the presence of positive-gain cycles, optimal paths are not necessarily simple. For dense graphs, our new Õ(n^{3.5}) time algorithm improves on a previous Õ(mn²)-time algorithm of Dorfman et al. [ESA 2023] for the problem. The gain of an arc is the amount of charge added to the battery of the car when traversing the arc. The charge in the battery can never exceed the capacity B of the battery and can never be negative. An arc of positive gain may correspond, for example, to a downhill road segment, while an arc with a negative gain may correspond to an uphill segment. A positive-gain cycle, if one exists, can be used in certain cases to charge the battery to its capacity. This makes the problem more interesting and more challenging. As mentioned, optimal energetic paths are well-defined even in the presence of positive-gain cycles. Positive-gain cycles may arise when certain road segments have magnetic charging strips, or when the electric car has solar panels. Combined with a result of Dorfman et al. [SOSA 2024], this also provides a randomized Õ(n^{3.5})-time algorithm for computing minimum-cost paths between all pairs of vertices in an n-vertex graph when the battery can be externally recharged, at varying costs, at intermediate vertices.

Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical. Hash functions are used everywhere in computing, e.g., hash tables, sketching, dimensionality reduction, sampling, and estimation. Many of these applications are relevant to Machine Learning, where we are often interested in similarity between high dimensional objects. Reducing the dimensionality is key to efficient processing. Abstractly, we like to think of hashing as fully-random hashing, assigning independent hash values to every possible key, but essentially this requires us to store the hash values for all keys, which is unrealistic for most key universes, e.g., 64-bit keys. In practice we have to settle for implementable hash functions, and often practitioners settle for implementations that are too simple in that the algorithms end up working only for sufficiently random input. However, the real world is full of structured/non-random input. The issue is severe, for simplistic hash functions will often work very well in tests with random input. Moreover, the issue is often that error events that should never happen in practice, happen with way too high probability. This does not show in a few tests, but will show up over time when you put the system into production. Over the last decade there has been major developments in simple to implement tabulation based hash functions offering strong theoretical guarantees, so as to support fundamental properties such as Chernoff bounds, Sparse Johnson-Lindenstrauss transforms, and fully-random hashing on a given set w.h.p. etc. I will discuss some of the principles of these developments and offer insights on how far we can bridge from theory (assuming fully-random hash functions) to practice (needing something that can actually implemented efficiently).

In the Correlation Clustering problem we are given n nodes, and a preference for each pair of nodes indicating whether we prefer the two endpoints to be in the same cluster or not. The output is a clustering inducing the minimum number of violated preferences. In certain cases, however, the preference between some pairs may be too important to be violated. The constrained version of this problem specifies pairs of nodes that must be in the same cluster as well as pairs that must not be in the same cluster (hard constraints). The output clustering has to satisfy all hard constraints while minimizing the number of violated preferences. Constrained Correlation Clustering is APX-Hard and has been approximated within a factor 3 by van Zuylen et al. [SODA’07]. Their algorithm is based on rounding an LP with Θ(n3) constraints, resulting in an Ω(n3ω) running time. In this work, using a more combinatorial approach, we show how to approximate this problem significantly faster at the cost of a slightly weaker approximation factor. In particular, our algorithm runs in Oe(n3) time (notice that the input size is Θ(n2)) and approximates Constrained Correlation Clustering within a factor 16. To achieve our result we need properties guaranteed by a particular influential algorithm for (unconstrained) Correlation Clustering, the CC-PIVOT algorithm. This algorithm chooses a pivot node u, creates a cluster containing u and all its preferred nodes, and recursively solves the rest of the problem. It is known that selecting pivots at random gives a 3-approximation. As a byproduct of our work, we provide a derandomization of the CC-PIVOT algorithm that still achieves the 3-approximation; furthermore, we show that there exist instances where no ordering of the pivots can give a (3 − ε)-approximation, for any constant ε. Finally, we introduce a node-weighted version of Correlation Clustering, which can be approximated within factor 3 using our insights on Constrained Correlation Clustering. As the general weighted version of Correlation Clustering would require a major breakthrough to approximate within a factor o(log n), Node-Weighted Correlation Clustering may be a practical alternative.

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. CCL+24 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, CCL+24 showed how to find a feasible solution for the cluster LP in time $O(n^{\text{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.485+ε)$-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 $\widetilde O(2^{\text{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.485+ε)$-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.

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.

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].

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.

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/· no(1). We balance our main result with the best-known semi-definite(SDP) approach which we use for degrees below n0.605073. As a result, we show that (n0.19747) colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of (n0.19996) by Kawarabayashi and Thorup from 2017.

We consider the numerical taxonomy problem of fitting a positive distance function \({\mathcal {D}:{S\choose 2}\rightarrow \mathbb {R}_{\gt 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 thebranching 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.”

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.

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.

A classical problem in computational geometry and graph algorithms is: given a dynamic set 𝒮 of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of 𝒮. Previous papers studied the setting where, before the updates, the data structure receives some parameter P. Then, updates could insert and delete disks as long as at all times the disks have a diameter that lies in a fixed range [1/P, 1]. As a consequence of that prerequisite, the aspect ratio ψ (i.e. the ratio between the largest and smallest diameter) of the disks would at all times satisfy ψ ≤ P. The state-of-the-art for storing disks in a dynamic connectivity data structure is a data structure that uses O(Pn) space and that has amortized O(P log⁴ n) expected amortized update time. Connectivity queries between disks are supported in O(log n / log log n) time. In the dynamic setting, one wishes for a more flexible data structure in which disks of any diameter may arrive and leave, independent of their diameter, changing the aspect ratio freely. Ideally, the aspect ratio should merely be part of the analysis. We restrict our attention to axis-aligned squares, and study fully-dynamic square intersection graph connectivity. Our result is fully-adaptive to the aspect ratio, spending time proportional to the current aspect ratio ψ, as opposed to some previously given maximum P. Our focus on squares allows us to simplify and streamline the connectivity pipeline from previous work. When n is the number of squares and ψ is the aspect ratio after insertion (or before deletion), our data structure answers connectivity queries in O(log n / log log n) time. We can update connectivity information in O(ψ log⁴ n + log⁶ n) amortized time. We also improve space usage from O(P ⋅ n log n) to O(n log³ n log ψ) - while generalizing to a fully-adaptive aspect ratio - which yields a space usage that is near-linear in n for any polynomially bounded ψ.

The Sparse Johnson-Lindenstrauss Transform of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map A ∈ ℝ^{m × u} in 𝓁₂ that preserves distances up to distortion of 1 + ε with probability 1 - δ, where m = O(ε^{-2} log 1/δ) and each column of A has O(ε m) non-zero entries. The previous analyses of the Sparse Johnson-Lindenstrauss Transform all assumed access to a Ω(log 1/δ)-wise independent hash function. The main contribution of this paper is a more general analysis of the Sparse Johnson-Lindenstrauss Transform with less assumptions on the hash function. We also show that the Mixed Tabulation hash function of Dahlgaard, Knudsen, Rotenberg, and Thorup (FOCS 2015) satisfies the conditions of our analysis, thus giving us the first analysis of a Sparse Johnson-Lindenstrauss Transform that works with a practical hash function.

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 Õ(m1-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].

Simple tabulation hashing dates back to Zobrist in 1970 and is defined as follows: Each key is viewed as $c$ characters from some alphabet $Σ$, we have $c$ fully random hash functions $h_0, \ldots, h_{c - 1} \colon Σ\to \{0, \ldots, 2^l - 1\}$, and a key $x = (x_0, \ldots, x_{c - 1})$ is hashed to $h(x) = h_0(x_0) \oplus \ldots \oplus h_{c - 1}(x_{c - 1})$ where $\oplus$ is the bitwise XOR operation. The previous results on tabulation hashing by P{\v a}tra{\c s}cu and Thorup~[J.ACM'11] and by Aamand et al.~[STOC'20] focused on proving Chernoff-style tail bounds on hash-based sums, e.g., the number keys hashing to a given value, for simple tabulation hashing, but their bounds do not cover the entire tail. Chaoses are random variables of the form $\sum a_{i_0, \ldots, i_{c - 1}} X_{i_0} \cdot \ldots \cdot X_{i_{c - 1}}$ where $X_i$ are independent random variables. Chaoses are a well-studied concept from probability theory, and tight analysis has been proven in several instances, e.g., when the independent random variables are standard Gaussian variables and when the independent random variables have logarithmically convex tails. We notice that hash-based sums of simple tabulation hashing can be seen as a sum of chaoses that are not independent. This motivates us to use techniques from the theory of chaoses to analyze hash-based sums of simple tabulation hashing. In this paper, we obtain bounds for all the moments of hash-based sums for simple tabulation hashing which are tight up to constants depending only on $c$. In contrast with the previous attempts, our approach will mostly be analytical and does not employ intricate combinatorial arguments. The improved analysis of simple tabulation hashing allows us to obtain bounds for the moments of hash-based sums for the mixed tabulation hashing introduced by Dahlgaard et al.~[FOCS'15].

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.

In this paper, we consider the problems from the area of sublinear-time algorithms of edge sampling, edge counting, and triangle counting. Part of our contribution is that we consider three different settings, differing in the way in which one may access the neighborhood of a given vertex. In previous work, people have considered indexed neighbor access, with a query returning the i-th neighbor of a given vertex. Full neighborhood access model, which has a query that returns the entire neighborhood at a unit cost, has recently been considered in the applied community. Between these, we propose hash-ordered neighbor access, inspired by coordinated sampling, where we have a global fully random hash function, and can access neighbors in order of their hash values, paying a constant for each accessed neighbor.

Stochastic sample-based estimators are among the most fundamental and universally applied tools in statistics. Such estimators are particularly important when processing huge amounts of data, where we need to be able to answer a wide range of statistical queries reliably, yet cannot afford to store the data in its full length. In many applications we need the sampling to be coordinated which is typically attained using hashing. In previous work, a common strategy to obtain reliable sample-based estimators that work within certain error bounds with high probability has been to design one that works with constant probability, and then boost the probability by taking the median over r independent repetitions. Aamand et al. (STOC'20) recently proposed a fast and practical hashing scheme with strong concentration bounds , Tabulation-1Permutation, the first of its kind. In this paper, we demonstrate that using such a hash family for the sampling, we achieve the same high probability bounds without any need for repetitions. Using the same space, this saves a factor r in time, and simplifies the overall algorithms. We validate our approach experimentally on both real and synthetic data. We compare Tabulation-1Permutation with other hash functions such as strongly universal hash functions and various other hash functions such as MurmurHash3 and BLAKE3, both with and without resorting to repetitions. We see that if we want reliability in terms of small error probabilities, then Tabulation-1Permutation is significantly faster.

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”.

In dynamic load balancing, we wish to distribute balls into bins in an environment where both balls and bins can be added and removed. We want to minimize the maximum load of any bin but we also want to minimize the number of balls and bins that are affected when adding or removing a ball or a bin. We want a hashing-style solution where we given the ID of a ball can find its bin efficiently.

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 probability1: Two sequential algorithms with complexities O(m log n) and O(m + n log3 n). These improve on a long line of developments including a celebrated O(m log3 n) algorithm of Karger [STOC'96] and the state of the art O(m log2 n(log log n)2) algorithm of Henzinger et al. [SODA'17]. Moreover, our O(m + n log3 n) algorithm is optimal when m = Ω (n log3 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.

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 ≪ |Σ|.

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.

Consider collections $\mathcal{A}$ and $\mathcal{B}$ of red and blue sets, respectively. Bichromatic Closest Pair is the problem of finding a pair from $\mathcal{A}\times \mathcal{B}$ that has similarity higher than a given threshold according to some similarity measure. Our focus here is the classic Jaccard similarity $|\textbf{a}\cap \textbf{b}|/|\textbf{a}\cup \textbf{b}|$ for $(\textbf{a},\textbf{b})\in \mathcal{A}\times \mathcal{B}$. We consider the approximate version of the problem where we are given thresholds $j_1>j_2$ and wish to return a pair from $\mathcal{A}\times \mathcal{B}$ that has Jaccard similarity higher than $j_2$ if there exists a pair in $\mathcal{A}\times \mathcal{B}$ with Jaccard similarity at least $j_1$. The classic locality sensitive hashing (LSH) algorithm of Indyk and Motwani (STOC '98), instantiated with the MinHash LSH function of Broder et al., solves this problem in $\tilde O(n^{2-δ})$ time if $j_1\ge j_2^{1-δ}$. In particular, for $δ=Ω(1)$, the approximation ratio $j_1/j_2=1/j_2^δ$ increases polynomially in $1/j_2$. In this paper we give a corresponding hardness result. Assuming the Orthogonal Vectors Conjecture (OVC), we show that there cannot be a general solution that solves the Bichromatic Closest Pair problem in $O(n^{2-Ω(1)})$ time for $j_1/j_2=1/j_2^{o(1)}$. Specifically, assuming OVC, we prove that for any $δ>0$ there exists an $\varepsilon>0$ such that Bichromatic Closest Pair with Jaccard similarity requires time $Ω(n^{2-δ})$ for any choice of thresholds $j_2

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.

We consider word RAM data structures for maintaining ordered sets of integers whose select and rank operations are allowed to return approximate results, i.e., ranks, or items whose rank, differ by less than Delta from the exact answer, where Delta=Delta(n) is an error parameter. Related to approximate select and rank is approximate (one-dimensional) nearest-neighbor. A special case of approximate select queries are approximate min queries. Data structures that support approximate min operations are known as approximate heaps (priority queues). Related to approximate heaps are soft heaps, which are approximate heaps with a different notion of approximation. We prove the optimality of all the data structures presented, either through matching cell-probe lower bounds, or through equivalences to well studied static problems. For approximate select, rank, and nearest-neighbor operations we get matching cell-probe lower bounds. We prove an equivalence between approximate min operations, i.e., approximate heaps, and the static partitioning problem. Finally, we prove an equivalence between soft heaps and the classical sorting problem, on a smaller number of items. Our results have many interesting and unexpected consequences. It turns out that approximation greatly speeds up some of these operations, while others are almost unaffected. In particular, while select and rank have identical operation times, both in comparison-based and word RAM implementations, an interesting separation emerges between the approximate versions of these operations in the word RAM model. Approximate select is much faster than approximate rank. It also turns out that approximate min is exponentially faster than the more general approximate select. Next, we show that implementing soft heaps is harder than implementing approximate heaps. The relation between them corresponds to the relation between sorting and partitioning. Finally, as an interesting byproduct, we observe that a combination of known techniques yields a deterministic word RAM algorithm for (exactly) sorting n items in O(n log log_w n) time, where w is the word length. Even for the easier problem of finding duplicates, the best previous deterministic bound was O(min{n log log n,n log_w n}). Our new unifying bound is an improvement when w is sufficiently large compared with n.

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.

We present a deterministic algorithm that computes the edge-connectivity of a graph in near-linear time. This is 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. Our algorithm is easily extended to find a concrete minimum edge-cut. In fact, we can construct the classic cactus representation of all minimum cuts in near-linear time. The previous fastest deterministic algorithm by Gabow from STOC '91 took Õ( m +λ 2 n ), where λ is the edge connectivity, but λ can be as big as n −1. Karger presented a randomized near-linear time Monte Carlo algorithm for the minimum cut problem at STOC’96, but the returned cut is only minimum with high probability. Our main technical contribution is a near-linear time algorithm that contracts vertex sets of a simple input graph G with minimum degree Δ, producing a multigraph Ḡ with Õ( m /Δ) edges, which preserves all minimum cuts of G with at least two vertices on each side. In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS’06. Normally, such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.

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.

Suppose that we are to place $m$ balls into $n$ bins sequentially using the $d$-choice paradigm: For each ball we are given a choice of $d$ bins, according to $d$ hash functions $h_1,\dots,h_d$ and we place the ball in the least loaded of these bins breaking ties arbitrarily. Our interest is in the number of balls in the fullest bin after all $m$ balls have been placed. Azar et al. [STOC'94] proved that when $m=O(n)$ and when the hash functions are fully random the maximum load is at most $\frac{\lg \lg n }{\lg d}+O(1)$ whp (i.e. with probability $1-O(n^{-γ})$ for any choice of $γ$). In this paper we suppose that the $h_1,\dots,h_d$ are simple tabulation hash functions. Generalising a result by Dahlgaard et al [SODA'16] we show that for an arbitrary constant $d\geq 2$ the maximum load is $O(\lg \lg n)$ whp, and that expected maximum load is at most $\frac{\lg \lg n}{\lg d}+O(1)$. We further show that by using a simple tie-breaking algorithm introduced by Vöcking [J.ACM'03] the expected maximum load drops to $\frac{\lg \lg n}{d\lg φ_d}+O(1)$ where $φ_d$ is the rate of growth of the $d$-ary Fibonacci numbers. Both of these expected bounds match those of the fully random setting. The analysis by Dahlgaard et al. relies on a proof by Pătraşcu and Thorup [J.ACM'11] concerning the use of simple tabulation for cuckoo hashing. We need here a generalisation to $d>2$ hash functions, but the original proof is an 8-page tour de force of ad-hoc arguments that do not appear to generalise. Our main technical contribution is a shorter, simpler and more accessible proof of the result by Pătraşcu and Thorup, where the relevant parts generalise nicely to the analysis of $d$ choices.

When deciding where to place access points in a wireless network, it is useful to model the signal propagation loss between a proposed antenna location and the areas it may cover. The indoor dominant path (IDP) model, introduced by Wölfle et al., is shown in the literature to have good validation and generalization error, is faster to compute than competing methods, and is used in commercial software such as WinProp, iBwave Design, and CellTrace. The previous algorithms known for computing it involved a worst-case exponential-time tree search, with pruning heuristics for speed.

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

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 ith 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.

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.

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.

A random sampling function ${\it Sample}:U\rightarrow\{0,1\}$ for a key universe $U$ is a distinguisher with probability $\alpha$ if for any given assignment of values $v(x)$ to the keys $x\in U$, including at least one nonzero $v(x)\neq0$, the sampled sum $\sum_{x\in U}{\it Sample}(x)v(x)$ is nonzero with probability at least $\alpha$. 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 [ Randomness, Adversaries, and Computation, Ph.D. thesis, University of California, Berkeley, CA, 1986], and Naor and Naor used them for their small-bias probability spaces [ SIAM J. Comput., 22 (1993), pp. 838--856]. Constant probability distinguishers are used for testing in contexts where the individual 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),\ldots,(x_n,v_n)$ where the same key may appear many times. The accumulated value of key $x$ is $v(x)=\sum_{i\in \{1,\ldots,n \}, x_i=x} v_i$, and we want to check if there is any nonzero $v(x)$ (a nonzero could indicate some accounting mistake). For space reasons, we may not be able to maintain $v(x)$ for every key $x$, but the sampled sum is easily maintained as the single value $\sum_{i=1}^n{\it Sample}(x_i)v_i$. 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 $\textit{Sample}(x)=[ax \mod 2^w\leq 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 \texttta*x<=t. Previous such samplers were much less computer friendly; e.g., the distinguisher of Naor and Naor [ SIAM J. Comput., 22 (1993), pp. 838--856] was more complicated and involved a 7-independent hash function.

We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with O (log 3 n log log 2 n ) amortized time per edge insertion and O (1) query time. This result partially answers an open question posed by Thorup (2007). It also stays in sharp contrast to a polynomial conditional lower bound for the fully dynamic weighted minimum cut problem. Our algorithm is obtained by combining a sparsification technique of Kawarabayashi and Thorup (2015) or its recent improvement by Henzinger, Rao, and Wang (2017), and an exact incremental algorithm of Henzinger (1997). We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O ( n log n /ε 2 ) space Monte Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a (1+ε)-approximation to the minimum cut. The algorithm has O ((α ( n ) log 3 n )/ε 2 ) amortized update time and constant query time, where α ( n ) stands for the inverse of Ackermann function.

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.

Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical. Here we survey recent results on how simple hashing schemes based on tabulation provide unexpectedly strong guarantees.

Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical. Here we survey recent results on how simple hashing schemes based on tabulation provide unexpectedly strong guarantees. Simple tabulation hashing dates back to Zobrist [1970]. Keys are viewed as consisting of c characters and we have precomputed character tables h_1,...,h_q mapping characters to random hash values. A key x=(x_1,...,x_c) is hashed to h_1[x_1] xor h_2[x_2]..... xor h_c[x_c]. This schemes is very fast with character tables in cache. While simple tabulation is not even 4-independent, it does provide many of the guarantees that are normally obtained via higher independence, e.g., linear probing and Cuckoo hashing. Next we consider twisted tabulation where one character is "twisted" with some simple operations. The resulting hash function has powerful distributional properties: Chernoff-Hoeffding type tail bounds and a very small bias for min-wise hashing. Finally, we consider double tabulation where we compose two simple tabulation functions, applying one to the output of the other, and show that this yields very high independence in the classic framework of Carter and Wegman [1977]. In fact, w.h.p., for a given set of size proportional to that of the space consumed, double tabulation gives fully-random hashing. While these tabulation schemes are all easy to implement and use, their analysis is not. This keynote talk surveys results from the papers in the reference list.

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.

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We first present a new combinatorial algorithm using Õ ( n 4/11 ) colors. This is the first combinatorial improvement since Blum’s Õ ( n 3/8 ) bound from FOCS’90. Like Blum’s algorithm, our new algorithm composes immediately with recent semi-definite programming approaches, and improves the best bound for the polynomial time algorithm for the coloring of 3-colorable graphs from O ( n 0.2072 ) colors by Chlamtac from FOCS’07 to O ( n 0.2049 ) colors. Next, we develop a new recursion tailored for combination with semi-definite approaches, bringing us further down to O ( n 0.19996 ) colors.

We describe an algorithm for solving an important geometric problem arising in computer-aided manufacturing. When machining a pocket in a solid piece of material such as steel using a rough tool in a milling machine, sharp convex corners of the pocket cannot be done properly, but have to be left for finer tools that are more expensive to use. We want to determine a tool path that maximizes the use of the rough tool. Mathematically, this boils down to the following problem. Given a simply-connected set of points P in the plane such that the boundary of P is a curvilinear polygon consisting of n line segments and circular arcs of arbitrary radii, compute the maximum subset Q of P consisting of simply-connected sets where the boundary of each set is a curve with bounded convex curvature. A closed curve has bounded convex curvature if, when traversed in counterclockwise direction, it turns to the left with curvature at most 1. There is no bound on the curvature where it turns to the right. The difference in the requirement to left- and right-curvature is a natural consequence of different conditions when machining convex and concave areas of the pocket. We devise an algorithm to compute the unique maximum such set Q. The algorithm runs in O(n log n) time and uses O(n) space. For the correctness of our algorithm, we prove a new generalization of the Pestov-Ionin Theorem. This is needed to show that the output Q of our algorithm is indeed maximum in the sense that if Q' is any subset of P with a boundary of bounded convex curvature, then Q' is a subset of Q.

We present a deterministic incremental algorithm for \textit{exactly} maintaining the size of a minimum cut with $\widetilde{O}(1)$ amortized time per edge insertion and $O(1)$ query time. This result partially answers an open question posed by Thorup [Combinatorica 2007]. It also stays in sharp contrast to a polynomial conditional lower-bound for the fully-dynamic weighted minimum cut problem. Our algorithm is obtained by combining a recent sparsification technique of Kawarabayashi and Thorup [STOC 2015] and an exact incremental algorithm of Henzinger [J. of Algorithm 1997]. We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an ${O}(n\log n/\varepsilon^2)$ space Monte-Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a $(1+\varepsilon)$-approximation to the minimum cut. The algorithm has $\widetilde{O}(1)$ amortized update-time and constant query-time.

We present a deterministic dynamic connectivity data structure for undirected graphs with worst case update time O(sqrt{(n(log(log(n)))^2)/log(n)}) and constant query time. This improves on the previous best deterministic worst case algorithm of Frederickson (SIAM J. Comput., 1985) and Eppstein Galil, Italiano, and Nissenzweig (J. ACM, 1997), which had update time O(sqrt{n}). All other algorithms for dynamic connectivity are either randomized (Monte Carlo) or have only amortized performance guarantees.

We develop a new algorithm for the turnstile heavy hitters problem in general turnstile streams, the EXPANDERSKETCH, which finds the approximate top- k items in a universe of size n using the same asymptotic O ( k log n ) words of memory and O (log n ) update time as the COUNTMIN and COUNTSKETCH, but requiring only O ( k poly (log n )) time to answer queries instead of the O ( n log n ) time of the other two. The notion of "approximation" is the same l 2 sense as the COUNTSKETCH, which given known lower bounds is the strongest guarantee one can achieve in sublinear memory. Our main innovation is an efficient reduction from the heavy hitters problem to a clustering problem in which each heavy hitter is encoded as some form of noisy spectral cluster in a 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 pieces while finding every cluster. To do this we first apply standard spectral graph partitioning, and then we use some novel local search techniques to modify the cuts obtained so as to make sure that the original clusters are sufficiently preserved. Our clustering algorithm may be of broader interest beyond heavy hitters and streaming algorithms.

Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical. Here we survey recent results on how simple hashing schemes based on tabulation provide unexpectedly strong guarantees. Simple tabulation hashing dates back to Zobrist [1970]. Keys are viewed as consisting of c characters and we have precomputed character tables h_1, ... , h_q mapping characters to random hash values. A key x = (x_1 , ..., x_c) is hashed to h_1[x_1] + h_2[x_2] ... + h_c[x_c]. This scheme is very fast with character tables in cache. While simple tabulation is not even 4-independent, it does provide many of the guarantees that are normally obtained via higher independence, e.g., linear probing and Cuckoo hashing. Next we consider twisted tabulation where one character is "twisted" with some simple operations. The resulting hash function has powerful distributional properties: Chernoff-Hoeffding type tail bounds and a very small bias for min-wise hashing. Finally, we consider double tabulation where we compose two simple tabulation functions, applying one to the output of the other, and show that this yields very high independence in the classic framework of Carter and Wegman [1977]. In fact, w.h.p., for a given set of size proportional to that of the space consumed, double tabulation gives fully-random hashing. While these tabulation schemes are all easy to implement and use, their analysis is not.

The power of two choices is a classic paradigm for load balancing when assigning m balls to n bins. When placing a ball, we pick two bins according to two hash functions h0 and h1, and place the ball in the least loaded bin. Assuming fully random hash functions, when m = O(n), Azar et al. [STOC'94] proved that the maximum load is lg lg n + O(1) with high probability. No such bound was known with a hash function implementable in constant time. In this paper, we investigate the power of two choices when the hash functions h0 and h1 are implemented with simple tabulation, which is a very efficient hash function evaluated in constant time. Following their analysis of Cuckoo hashing [J.ACM'12], Pâtraşcu and Thorup claimed that the expected maximum load with simple tabulation is O(lg lg n). This did not include any high probability guarantee, so the load balancing was not yet to be trusted. Here, we show that with simple tabulation, the maximum load is O(lg lg n) with high probability, giving the first constant time hash function with this guarantee. We also give a concrete example where, unlike with fully random hashing, the maximum load is not bounded by lg lg n + O(1), or even (1 + o(1)) lg lg n with high probability. Finally, we show that the expected maximum load is lg lg n + O(1), just like with fully random hashing.

Gabow and Tarjan showed that the Bottleneck Path (BP) problem, i.e., finding a path between a given source and a given target in a weighted directed graph whose largest edge weight is minimized, as well as the Bottleneck spanning tree (BST) problem, i.e., finding a directed spanning tree rooted at a given vertex whose largest edge weight is minimized, can both be solved deterministically in O(m * log^*(n)) time, where m is the number of edges and n is the number of vertices in the graph. We present a slightly improved randomized algorithm for these problems with an expected running time of O(m * beta(m,n)), where beta(m,n) = min{k >= 1 | log^{(k)}n <= m/n } <= log^*(n) - log^*(m/n)+1. This is the first improvement for these problems in over 25 years. In particular, if m >= n * log^{(k)} * n, for some constant k, the expected running time of the new algorithm is O(m). Our algorithm, as that of Gabow and Tarjan, work in the comparison model. We also observe that in the word-RAM model, both problems can be solved deterministically in O(m) time. Finally, we solve an open problem of Andersson et al., giving a deterministic O(m)-time comparison-based algorithm for solving deterministic 2-player turn-based zero-sum terminal payoff games, also known as Deterministic Graphical Games (DGG).

We show that linear probing requires 5-independent hash functions for expected constant-time performance, matching an upper bound of Pagh et al. [2009]. More precisely, we construct a random 4-independent hash function yielding expected logarithmic search time for certain keys. For (1 + ϵ)-approximate minwise independence, we show that Ω(lg 1/ϵ)-independent hash functions are required, matching an upper bound of Indyk [2001]. We also show that the very fast 2-independent multiply-shift scheme of Dietzfelbinger [1996] fails badly in both applications.

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.

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].

A random sampling functionSample:U→ {0, 1} for a key universeUis adistinguisher with probability. If for any given assignment of valuesv(x) to the keysx∈U, including at least one non-zerov(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 (x1,v1), (x2,v2), ..., (xn,vn) where the same key may appear many times. The accumulated value of keyxisv(x) = Σ{v1|xi=x}. For space reasons, we may not be able to maintainx(x) for every keyx, but the sampled sum is easily maintained as the single value Σ{vi|Sample(xi) = 1}. Here we show that when dealing withw-bit integers, ifais a uniform oddw-bit integer andtis a uniformw-bit integer, thenSample(x) = [axmod 2w≤t] is a distinguisher with probability 1/8. Working with standard units, that isw= 8,16,32,64, we exploit thatw-bit multiplication works modulo 2w, 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.

In the CONGEST model, a communications network is an undirected graph whose n nodes are processors and whose m edges are the communications links between processors. At any given time step, a message of size O(log n) may be sent by each node to each of its neighbours. We show for the synchronous model: If all nodes start in the same round, and each node knows its ID and the ID's of its neighbors, or in the case of MST, the distinct weights of its incident edges and knows n, then there are Monte Carlo algorithms which succeed w.h.p. to determine a minimum spanning forest (MST) and a spanning forest (ST) using O(n log2 n/log log n) messages for MST and O(n log n) messages for ST, resp. These results contradict the "folk theorem" noted in Awerbuch, et.al., JACM 1990 that the distributed construction of a broadcast tree requires Ω(m) messages. This lower bound has been shown there and in other papers for some CONGEST models; our protocol demonstrates the limits of these models.

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(2n/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.

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.

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.

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.

Recognizing 3-colorable graphs is one of the most famous NP-complete problems [Garey, Johnson, and Stockmeyer, STOC'74]. The problem of coloring 3-colorable graphs in polynomial time with as few colors as possible has been intensively studied: O(n^{1/2}) colors [Wigderson, STOC'82], O(n^{2/5}) colors [Blum, STOC'89], O(n^{3/8}) colors [Blum, FOCS'90], O(n^{1/4}) colors [Karger, Motwani and Sudan, FOCS'94], O(n^{3/14})=O(n^0.2142) colors [Blum and Karger, IPL'97], O(n^{0.2111}) colors [Arora, Chlamtac, and Charikar, STOC'06], and O(n^{0.2072}) colors [Chlamtac, FOCS'07]. Recently the authors got down to O(n^{0.2049}) colors [FOCS'12]. In this paper we get down to O(n^{0.19996})=o(n^{1/5}) colors. Since 1994, the best bounds have all been obtained balancing between combinatorial and semi-definite approaches. We present a new combinatorial recursion that only makes sense in collaboration with semi-definite programming. We specifically target the worst-case for semi-definite programming: high degrees. By focusing on the interplay, we obtained the biggest improvement in the exponent since 1997.

A union-find data structure maintains a collection of disjoint sets under the operations makeset, union, and find. Kaplan, Shafrir, and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which items of the sets maintained may be deleted. The cost of a delete operation in their implementations is essentially the same as the cost of a find operation; namely, O (log n ) worst-case and O (α ⌈ M / N ⌉ ( n )) amortized, where n is the number of items in the set returned by the find operation, N is the total number of makeset operations performed, M is the total number of find operations performed, and α ⌈ M / N ⌉ ( n ) is a functional inverse of Ackermann’s function. They left open the question whether delete operations can be implemented more efficiently than find operations, for example, in o (log n ) worst-case time. We resolve this open problem by presenting a relatively simple modification of the classical union-find data structure that supports delete, as well as makeset and union operations, in constant worst-case time, while still supporting find operations in O (log n ) worst-case time and O (α ⌈ M/N⌉ ( n )) amortized time. Our analysis supplies, in particular, a very concise potential-based amortized analysis of the standard union-find data structure that yields an O (α ⌈ M / N ⌉ ( n )) amortized bound on the cost of find operations. All previous potential-based analyses yielded the weaker amortized bound of O (α ⌈ M / N ⌉ ( N )). Furthermore, our tighter analysis extends to one-path variants of the path compression technique such as path splitting .

Bottom-k sketches are an alternative to k×minwise sketches when using hashing to estimate the similarity of documents represented by shingles (or set similarity in general) in large-scale machine learning. They are faster to compute and have nicer theoretical properties. In the case of k×minwise hashing, the bias introduced by not truly random hash function is independent of the number k of hashes, while this bias decreases with increasing k when employing bottom-k. In practice, bottom-k sketches can expedite classification systems if the trained classifiers are applied to many data points with a lot of features (i.e., to many documents encoded by a large number of shingles on average). An advantage of b-bit k×minwise hashing is that it can be efficiently incorporated into machine learning methods relying on scalar products, such as support vector machines (SVMs). Still, experimental results indicate that a nearest neighbors classifier with bottom-k sketches can be preferable to using a linear SVM and b-bit k×minwise hashing if the amount of training data is low or the number of features is high.

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 h0, ... , hc-1mapping characters to random hash values. A key x = (x0, ... , xc-1) is hashed to h0[x0]⊕· · ·⊕hc-1[xc-1], where ⊕ denotes bit-wise exclusive-or. The scheme is extremely fast when the character hash tables hiare 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)cevaluation 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(clogc)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.

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.

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).

We consider bottom-k sampling for a set X, picking a sample Sk(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 |Sk(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 Sk(A union B)=Sk(Sk(A) union Sk(B)), and then the similarity is estimated as |Sk(A union B) intersect Sk(A) intersect Sk(B)|/k.

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 Õ(n4/11) colors. This is the first combinatorial improvement of Blum's Õ(n3/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 Õ(n0.2072) colors by Chlamtac from FOCS'07. We now bring it down to Õ(n0. 2049) colors.

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) = Õ(m1+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 Ω̃(m5/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.

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 Zobrist in 1970 who used it for game playing programs. Keys are viewed as consisting of c characters. We initialize c tables H 1, ..., H c mapping characters to random hash codes. A key x = ( x 1 , ..., x c ) is hashed to H 1[ x 1] ⊕ ⋯ ⊕ H c [ x c ], where ⊕ denotes bit-wise exclusive-or. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, for example, Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing.

In the framework of Wegman and Carter, a k-independent hash function maps any k keys independently. It is known that 5-independent hashing provides good expected performance in applications such as linear probing and second moment estimation for data streams. The classic 5-independent hash function evaluates a degree 4 polynomial over a prime field containing the key domain $[n]=\{0,\ldots,n-1\}$. Here we present an efficient 5-independent hash function that uses no multiplications. Instead, for any parameter c, we make $2c-1$ lookups in tables of size $O(n^{1/c})$. In experiments on different computers, our scheme gained factors of 1.8 to 10 in speed over the polynomial method. We also conducted experiments on the performance of hash functions inside the above applications. In particular, we give realistic examples of inputs that make the most popular 2-independent hash function perform quite poorly. This illustrates the advantage of using schemes with provably good expected performance for all inputs.

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.

We consider portable software implementations of hash tables with timeouts. The context is a high volume stream of keyed items. When a new item arrives, we want to know if has been seen recently in terms of a fixed lifespan. This problem has numerous applications as a front-end for Internet traffic processing where the key could be a selection of fields from the header of a packet, e.g., tracing packets through networks, aggregation of netflows from routers, and helping firewalls reuse decisions from recent packets with the same key. We propose time-reversed linear probing tables to deal with timeouts. In experiments, compared with tumbling windows and lazy deletions, our time-reversed tables typically gains at least 25% in speed while using only half the space. The cost per item approaches that of a single random memory access. Our new scheme is cleaner to implement than previous schemes, and also more versatile, e.g., it is trivial to allow different items to have different lifespans; something not possible with tumbling windows. Adding this to the improved time and space efficiency, makes time-reversed linear probing a canonical first choice for hash tables with time-outs.

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].

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 tu be the time to insert an edge and tq be the query time. For tu = Omega(tq), 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 tu = tq = O(lg n / lg lg n) and amortized tu = tq = O(α(n)). By contrast, we show that if tu = o(lg n / lg lg n), the query time explodes to tq ≥ n1-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!

From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, $\textnormal{\sc VarOptk}$, that dominates all previous schemes in terms of estimation quality. $\textnormal{\sc VarOptk}$ provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. It is efficient, handling each new item of the stream in $O(\log k)$ time. Finally, it is particularly well suited for combinations of samples from different streams in a distributed setting.

Previously [SODA'04] we devised the fastest known algorithm for 4-universal hashing. The hashing was based on small pre-computed 4-universal tables. This led to a five-fold improvement in speed over direct methods based on degree 3 polynomials. In this paper, we show that if the pre-computed tables are made 5-universal, then the hash value becomes 5-universal without any other change to the computation. Relatively this leads to even bigger gains since the direct methods for 5-universal hashing use degree 4 polynomials. Experimentally, we find that our method can gain up to an order of magnitude in speed over direct 5-universal hashing. Some of the most popular randomized algorithms have been proved to have the desired expected running time using 5-universal hashing, e.g., a non-recursive variant of quicksort takes O(n log n) expected time [Karloff Raghavan JACM'93], and linear probing does updates and searches in O(1) expected time [Pagh et al. SICOMP'09]. In contrast, inputs have been constructed leading to much worse expected performance with some of the classic primality based 2-universal hashing schemes. In the context of linear probing, we compare our new fast 5-universal hashing experimentally with the fastest known plain universal hashing. We know that any reasonable hashing scheme will work on random input, but from Pagh et al., we know that 5-universal hashing leads to good expected performance on all input. We use a dense interval as an example of a structured yet realistic input, wanting to see if this could push the fastest multiplication-shift based plain universal hashing into bad performance. Even though our 5-universal hashing itself is slower than the fast plain universal hashing, it makes linear probing much more robust.

Regular expression matching is a key task (and often computational bottleneck) in a variety of software tools and applications. For instance, the standard grep and sed utilities, scripting languages such as perl, internet traffic analysis, XML querying, and protein searching. The basic definition of a regular expression is that we combine characters with union, concatenation, and kleene star operators. The length m is proportional to the number of characters. However, often the initial operation is to concatenate characters in fairly long strings, e.g., if we search for certain combinations of words in a firewall. As a result, the number k of strings in the regular expression is significantly smaller than m. Our main result is a new algorithm that essentially replaces m with k in the complexity bounds for regular expression matching. More precisely, after an O(m log k) time and O(m) space preprocessing of the expression, we can match it in a string presented as a stream of characters in time per character, where w is the number of bits in a memory word. For large w, this corresponds to the previous best bound of . Prior to this work no O(k) bound per character was known. We further extend our solution to efficiently handle character class interval operators C{x, y}. Here, C is a set of characters and C{x, y}, where x and y are integers such that 0 ≤ x ≤ y, represents a string of length between x and y from C. These character class intervals generalize variable length gaps which are frequently used for pattern matching in computational biology applications.

We describe a simple, but powerful local encoding technique, implying two surprising results: 1. We show how to represent a vector of n values from some alphabet S using ceiling(n * log2 |S|) bits, such that reading or writing any entry takes O(1) time. This demonstrates, for instance, an "equivalence" between decimal and binary computers, and has been a central toy problem in the field of succinct data structures. Previous solutions required space of n * log2 |S| + n/logO(1) n bits for constant access. 2. Given a stream of n bits arriving online (for any n, not known in advance), we can output a *prefix-free* encoding that uses n + log2 n + O(loglog n) bits. The encoding and decoding algorithms only require O(log n) bits of memory, and run in constant time per word. This result is interesting in cryptographic applications, as prefix-free codes are the simplest counter-measure to extensions attacks on hash functions, message authentication codes and pseudorandom functions. Our result refutes a conjecture of [Maurer, Sjodin 2005] on the hardness of online prefix-free encodings.

We present algorithms for finding optimal strategies for discounted, infinite-horizon, Determinsitc Markov Decision Processes (DMDPs). Our fastest algorithm has a worst-case running time of O ( mn ), improving the recent bound of O ( mn 2 ) obtained by Andersson and Vorbyov [2006]. We also present a randomized O ( m 1/2 n 2 )-time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving an O ( mn 2 )-time algorithm that can be obtained using ideas of Papadimitriou and Tsitsiklis [1987].

From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, VarOptk, that dominates all previous schemes in terms of estimation quality. VarOptk provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. It is efficient, handling each new item of the stream in O(log k) time, which is optimal even on the word RAM. Finally, it is particularly well suited for combination of samples from different streams in a distributed setting.

We present two new algorithms for finding optimal strategies for discounted, infinite-horizon, Deterministic Markov Decision Processes (DMDP). The first one is an adaptation of an algorithm of Young, Tarjan and Orlin for finding minimum mean weight cycles. It runs in O(mn + n2 log n) time, where n is the number of vertices (or states) and m is the number of edges (or actions). The second one is an adaptation of a classical algorithm of Karp for finding minimum mean weight cycles. It runs in O(mn) time. The first algorithm has a slightly slower worst-case complexity, but is faster than the first algorithm in many situations. Both algorithms improve on a recent O(mn2)-time algorithm of Andersson and Vorobyov. We also present a randomized -time algorithm for finding Discounted All-Pairs Shortest Paths (DAPSP), improving several previous algorithms.

Linear probing is one of the most popular implementations of dynamic hash tables storing all keys in a single array. When we get a key, we first hash it to a location. Next we probe consecutive locations until the key or an empty location is found. At STOC'07, Pagh et al. presented data sets where the standard implementation of 2-universal hashing leads to an expected number of Ω(log n) probes. They also showed that with 5-universal hashing, the expected number of probes is constant. Unfortunately, we do not have 5-universal hashing for, say, variable length strings. When we want to do such complex hashing from a complex domain, the generic standard solution is that we first do collision free hashing (w.h.p.) into a simpler intermediate domain, and second do the complicated hash function on this intermediate domain. Our contribution is that for an expected constant number of linear probes, it is suffices that each key has O(1) expected collisions with the first hash function, as long as the second hash function is 5-universal. This means that the intermediate domain can be n times smaller, and such a smaller intermediate domain typically means that the overall hash function can be made simpler and at least twice as fast. The same doubling of hashing speed for O(1) expected probes follows for most domains bigger than 32-bit integers, e.g., 64-bit integers and fixed length strings. In addition, we study how the overhead from linear probing diminishes as the array gets larger, and what happens if strings are stored directly as intervals of the array. These cases were not considered by Pagh et al.

Many data sets occur as unaggregated data sets , where multiple data points are associated with each key. In the aggregate view of the data, the weight of a key is the sum of the weights of data points associated with the key. Examples are measurements of IP packet header streams, distributed data streams produced by events registered by sensor networks, and Web page or multimedia requests to context distribution servers. We aim to combine sampling and aggregation to provide accurate and efficient summaries of the aggregate view. However, data points are scattered in time or across multiple servers and hence aggregation is subject to resource constraints on the size of summaries that can be stored or transmitted. We develop a summarization framework for unaggregated data where summarization is a scalable and composable operator, and as such, can be tailored to meet resource constraints. Our summaries support unbiased estimates of the weight of subpopulations of keys specified using arbitrary selection predicates. While we prove that under such scenarios there is no variance optimal scheme, our estimators have the desirable properties that the variance is progressively closer to the minimum possible when applied to a "more" aggregated data set. An extensive evaluation using synthetic and real data sets shows that our summarization framework outperforms all existing schemes for this fundamental problem, even for the special and well-studied case of data streams.

We convert cell-probe lower bounds for polynomial space into stronger lower bounds 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 searching in large databases, 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.

Measurement, collection, and interpretation of network usage data commonly involves multiple stage of sampling and aggregation. Examples include sampling packets, aggregating them into flow statistics at a router, sampling and aggregation of usage records in a network data repository for reporting, query and archiving. Although unbiased estimates of packet, bytes and flows usage can be formed for each sampling operation, for many applications it is crucial to know the inherent estimation error. Previous work in this area has been limited mainly to analyzing the estimator variance for particular methods, e.g., independent packet sampling. However, the variance is of limited use for more general sampling methods, where the estimate may not be well approximated by a Gaussian distribution.

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(mk3 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(n2k) 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].

Dynamic shortest-path algorithms update the shortest paths taking into account a change in an arc weight. This paper describes a new generic technique that allows the reduction of heap sizes used by several dynamic single-destination shortest-path algorithms. For unit weight changes, the updates can be done without heaps. These reductions almost always reduce the computational times for these algorithms. In computational testing, several dynamic shortest-path algorithms with and without the heap-reduction technique are compared. Speedups of up to a factor of 1.8 were observed using the heap-reduction technique on random weight changes and of over a factor of five on unit weight changes. We compare as well with Dijkstra's algorithm, which recomputes the paths from scratch. With respect to Dijkstra's algorithm, speedups of up to five orders of magnitude are observed.

We consider the problem of preprocessing an edge-weighted directed graph G to answer queries that ask for the length and first hop of a shortest path from any given vertex x to any given vertex y avoiding any given vertex or edge. As a natural application, this problem models routing in networks subject to node or link failures. We describe a deterministic oracle with constant query time for this problem that uses $O(n^2\log n)$ space, where n is the number of vertices in G. The construction time for our oracle is $O(mn^{2} + n^{3}\log n)$. However, if one is willing to settle for $\Theta (n^{2.5})$ space, we can improve the preprocessing time to $O(mn^{1.5}+n^{2.5}\log n)$ while maintaining the constant query time. Our algorithms can find the shortest path avoiding a failed node or link in time proportional to the length of the path.

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a Õ (√n,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. This is optimal in a very strong sense. It is known that no compact routing using o ( n ) space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires Ω(√ n ,)space per node.

We introduce the notion of roundtrip-spanners of weighted directed graphs and describe efficient algorithms for their construction. We show that for every integer k ≥ 1 and any ϵ > 0, any directed graph on n vertices with edge weights in the range [1, W ] has a (2 k + ϵ)-roundtrip-spanner with O (min{( k 2 /ϵ) n 1 + 1/ k (log( nW ), ( k /ϵ) 2 n 1 + 1/ k ,(log n ) 2−1/ k }) edges. We then extend these constructions and obtain compact roundtrip routing schemes. For every integer k ≥ 1 and every ϵ > 0, we describe a roundtrip routing scheme that has stretch 4 k + ϵ, and uses at each vertex a routing table of size Õ (( k 2 /ϵ) n 1/ k log( nW )). We also show that any weighted directed graph with arbitrary/ positive edge weights has a 3-roundtrip-spanner with O ( n 3/2 ) edges. This result is optimal. Finally, we present a stretch 3 roundtrip routing scheme that uses local routing tables of size Õ ( n 1/2 ). This routing scheme is essentially optimal. The roundtrip-spanner constructions and the roundtrip routing schemes for directed graphs that we describe are only slightly worse than the best available spanners and routing schemes for undirected graphs. Our roundtrip routing schemes substantially improve previous results of Cowen and Wagner. Our results are obtained by combining ideas of Cohen, Cowen and Wagner, Thorup and Zwick, with some new ideas.

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.

Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on the traffic of arbitrary subpopulations of flows. It is therefore of great importance to collect the most accurate and informative summaries given the router's resource constraints. Cisco's sampled NetFlow, based on aggregating a sampled packet stream into flows, is the most widely deployed such system.

IP packet streams consist of multiple interleaving IP flows. Statistical summaries of these streams, collected for different measurement periods, are used for characterization of traffic, billing, anomaly detection, inferring traffic demands, configuring packet filters and routing protocols, and more. While queries are posed over the set of flows, the summarization algorithmis applied to the stream of packets. Aggregation of traffic into flows before summarization requires storage of per-flow counters, which is often infeasible. Therefore, the summary has to be produced over the unaggregated stream.

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. This leads to an optimal bound of O (√log n /log log n ) for searching and updating a dynamic set X of n integer keys in linear space. Searching X for an integer y means finding the maximum key in X which is smaller than or equal to y . This problem is equivalent to the standard text book problem of maintaining an ordered set. The best previous deterministic linear space bound was O (log n /log log n ) due to Fredman and Willard from STOC 1990. No better deterministic search bound was known using polynomial space. We also get the following worst-case linear space trade-offs between the number n , the word length W , and the maximal key U < 2 W : O (min log log n + log n /log W , log log n ⋅ log log U /log log log U ). These trade-offs are, however, not likely to be optimal. Our results are generalized to finger searching and string searching, providing optimal results for both in terms of n .

From a high-volume stream of weighted items, we want to create a generic sample of a certain limited size that we can later use to estimate the total weight of arbitrary subsets. Applied to Internet traffic analysis, the items could be records summarizing the flows of packets streaming by a router. Subsets could be flow records from different time intervals of a worm attack whose signature is later determined. The samples taken in the past thus allow us to trace the history of the attack even though the worm was unknown at the time of sampling. Estimation from the samples must be accurate even with heavy-tailed distributions where most of the weight is concentrated on a few heavy items. We want the sample to be weight sensitive, giving priority to heavy items. At the same time, we want sampling without replacement in order to avoid selecting heavy items multiple times. To fulfill these requirements we introduce priority sampling, which is the first weight-sensitive sampling scheme without replacement that works in a streaming context and is suitable for estimating subset sums. Testing priority sampling on Internet traffic analysis, we found it to perform an order of magnitude better than previous schemes. Priority sampling is simple to define and implement: we consider a steam of items i = 0,…, n − 1 with weights w i . For each item i , we generate a random number α i ∈ (0,1] and create a priority q i = w i /α i . The sample S consists of the k highest priority items. Let τ be the ( k + 1)th highest priority. Each sampled item i in S gets a weight estimate ŵ i = max{ w i , τ}, while nonsampled items get weight estimate ŵ i = 0. Magically, it turns out that the weight estimates are unbiased, that is, E[ ŵ i ] = w i , and by linearity of expectation, we get unbiased estimators over any subset sum simply by adding the sampled weight estimates from the subset. Also, we can estimate the variance of the estimates, and find, surprisingly, that the covariance between estimates ŵ i and ŵ j of different weights is zero. Finally, we conjecture an extremely strong near-optimality; namely that for any weight sequence, there exists no specialized scheme for sampling k items with unbiased weight estimators that gets smaller variance sum than priority sampling with k + 1 items. Szegedy settled this conjecture at STOC'06.

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 O ( S ( n )) 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. Asymptotically, this settles the complexity of priority queues in terms of that of sorting. Previously, at SODA'96, such a result was presented by the author for the special case of monotone priority queues where the minimum is not allowed to decrease. Besides nailing down the complexity of priority queues to that of sorting, and vice versa, our result yields several improved bounds for linear space integer priority queues with find-min in constant time: Deterministically . We get O (log log n ) update time using a sorting algorithm of Han from STOC'02. This improves the O ((log log n )(log log log n )) update time of Han from SODA'01. Randomized . We get O (√log log n ) expected update time using a randomized sorting algorithm of Han and Thorup from FOCS'02. This improves the O (log log n ) expected update time of Thorup from SODA'96. Deterministically in AC 0 (without multiplication) . For any ε > 0, we get O ((log log n ) 1+ε ) update time using an AC 0 sorting algorithm of Han and Thorup from FOCS'02. This improves the O ((log log n ) 2 ) update time of Thorup from SODA'98. Randomized in AC 0 . We get O (log log n ) expected update time using a randomized AC 0 sorting algorithm of Thorup from SODA'97. This improves the O ((log log n ) 1+ε ) expected update time of Thorup also from SODA'97. The above bounds assume that each integer is stored in a single word and that word operations take unit time as in the word RAM.

Abstract Internet protocol (IP) traffic follows rules established by routing protocols. Shortest path‐based protocols, such as Open Shortest Path First (OSPF), direct traffic based on arc weights assigned by the network operator. Each router computes shortest paths and creates destination tables used for routing flow on the shortest paths. If a router has multiple outgoing links on shortest paths to a given destination, it splits traffic evenly over these links. It is also the role of the routing protocol to specify how the network should react to changes in the network topology, such as arc or router failures. In such situations, IP traffic is rerouted through the shortest paths not traversing the affected part of the network. This article addresses the issue of assigning OSPF weights and multiplicities to each arc, aiming to design efficient OSPF‐routed networks with minimum total weighted multiplicity (multiplicity multiplied by the arc length) needed to route the required demand and handle any single arc or router failure. The multiplicities are limited to a discrete set of values, and we assume that the topology is given. We propose an evolutionary algorithm for this problem, and present results applying it to several real‐world problem instances. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 51–64 2007

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.

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(logbn, 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 • lgO(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 n1+e, a running time of O(lg l / lg lg l) was given by Beame and Fich [STOC'99].

We show that any priority queue data structure that supports insert , delete , and find-min operations in pq ( n ) amortized time, where n is an upper bound on the number of elements in the priority queue, can be converted into a priority queue data structure that also supports fast meld operations with essentially no increase in the amortized cost of the other operations. More specifically, the new data structure supports insert , meld and find-min operations in O (1) amortized time, and delete operations in O ( pq ( n ) + α( n )) amortized time, where α( n ) is a functional inverse of the Ackermann function, and where n this time is the total number of operations performed on all the priority queues. The construction is very simple. The meldable priority queues are obtained by placing a nonmeldable priority queues at each node of a union-find data structure. We also show that when all keys are integers in the range [1, N ], we can replace n in the bound stated previously by min{ n , N }.Applying this result to the nonmeldable priority queue data structures obtained recently by Thorup [2002b] and by Han and Thorup [2002] we obtain meldable RAM priority queues with O (log log n ) amortized time per operation, or O (√log log n ) expected amortized time per operation, respectively. As a by-product, we obtain improved algorithms for the minimum directed spanning tree problem on graphs with integer edge weights, namely, a deterministic O ( m log log n )-time algorithm and a randomized O ( m √log log n )-time algorithm. For sparse enough graphs, these bounds improve on the O ( m + n log n ) running time of an algorithm by Gabow et al. [1986] that works for arbitrary edge weights.

Suppose we have a large table T of items i, each with a weight wi, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random priority depending on its weight. Suppose we want to estimate the sum of an arbitrary subset I ⊆ T. For any q > 2, considering only the q highest priority items from I, we obtain an unbiased estimator of the sum whose relative standard deviation is O(1/√q). Thus to get an expected approximation factor of 1 ± ε, it suffices to consider O(1/±ε2) items from I. Our estimator needs no knowledge of the number of items in the subset I, but we can also estimate that number if we want to estimate averages.The above scheme performs the same role as the on-line aggregation of Hellerstein et al. (SIGMOD'97) but it has the advantage of having expected good performance for any possible sequence of weights. In particular, the performance does not deteriorate in the common case of heavy-tailed weight distributions. This point is illustrated experimentally both with real and synthetic data.We will also show that our approach can be used to improve Cohen's size estimation framework (FOCS'94).

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 Ω(n3log ⁄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 Õ(n2.75) time.

Let G = (V,E) be an undirected weighted graph with | V | = n and | E | = m . Let k ≥ 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, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k −1. A 1963 girth conjecture of Erdós, implies that Ω( n 1+1/ k ) space is needed in the worst case for any real stretch strictly smaller than 2 k +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 ).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.

Abstract Intradomain traffic engineering aims to make more efficient use of network resources within an autonomous system. Interior Gateway Protocols such as OSPF (Open Shortest Path First) and IS‐IS (Intermediate System‐Intermediate System) are commonly used to select the paths along which traffic is routed within an autonomous system. These routing protocols direct traffic based on link weights assigned by the network operator. Each router in the autonomous system computes shortest paths and creates destination tables used to direct each packet to the next router on the path to its final destination. Given a set of traffic demands between origin‐destination pairs, the OSPF weight setting problem consists of determining weights to be assigned to the links so as to optimize a cost function, typically associated with a network congestion measure. In this article, we propose a genetic algorithm with a local improvement procedure for the OSPF weight‐setting problem. The local improvement procedure makes use of an efficient dynamic shortest path algorithm to recompute shortest paths after the modification of link weights. We test the algorithm on a set of real and synthetic test problems, and show that it produces near‐optimal solutions. We compare the hybrid algorithm with other algorithms for this problem illustrating its efficiency and robustness. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(1), 36–56 2005

We design top trees as a new simpler interface for data structures maintaining information in a fully dynamic forest. We demonstrate how easy and versatile they are to use on a host of different applications. For example, we show how to maintain the diameter, center, and median of each tree in the forest. The forest can be updated by insertion and deletion of edges and by changes to vertex and edge weights. Each update is supported in O (log n ) time, where n is the size of the tree(s) involved in the update. Also, we show how to support nearest common ancestor queries and level ancestor queries with respect to arbitrary roots in O (log n ) time. Finally, with marked and unmarked vertices, we show how to compute distances to a nearest marked vertex. The latter has applications to approximate nearest marked vertex in general graphs, and thereby to static optimization problems over shortest path metrics.Technically speaking, top trees are easily implemented either with Frederickson's [1997a] topology trees or with Sleator and Tarjan's [1983] dynamic trees. However, we claim that the interface is simpler for many applications, and indeed our new bounds are quadratic improvements over previous bounds where they exist.

We present a simple black box that takes a priority queue Q which supports find-min, insert, and delete in x-time at most t . Here x-time may be worst-case, expected, or amortized. The black-box transforms Q into a priority queue Q * that supports find-min in constant time, insert in constant x-time, and delete in x-time O ( t ). Moreover, if Q supports dec-key in constant time, then so does Q *.

This paper deals with sampling objects from a large stream. Each object possesses a size, and the aim is to be able to estimate the total size of an arbitrary subset of objects whose composition is not known at the time of sampling. This problem is motivated from network measurements in which the objects are flow records exported by routers and the sizes are the number of packet or bytes reported in the record. Subsets of interest could be flows from a certain customer or flows from a worm attack. This paper introduces threshold sampling as a sampling scheme that optimally controls the expected volume of samples and the variance of estimators over any classification of flows. It provides algorithms for dynamic control of sample volumes and evaluates them on flow data gathered from a commercial Internet Protocol (IP) network. The algorithms are simple to implement and robust to variation in network conditions. The work reported here has been applied in the measurement infrastructure of the commercial IP network. To not have employed sampling would have entailed an order of magnitude greater capital expenditure to accommodate the measurement traffic and its processing.

Passive traffic measurement increasingly employs sampling at the packet level. Many high-end routers form flow statistics from a sampled substream of packets. Sampling controls the consumption of resources by the measurement operations. However, knowledge of the statistics of flows in the unsampled stream remains useful, for understanding both characteristics of source traffic, and consumption of resources in the network. This paper provides methods that use flow statistics formed from sampled packet stream to infer the frequencies of the number of packets per flow in the unsampled stream. A key task is to infer the properties of flows of original traffic that evaded sampling altogether. We achieve this through statistical inference, and by exploiting protocol level detail reported in flow records. We investigate the impact on our results of different versions of packet sampling.

Many network management applications use as their data traffic volumes differentiated by attributes such as IP address or port number. IP flow records are commonly collected for this purpose: these enable determination of fine-grained usage of network resources. However, the increasingly large volumes of flow statistics incur concomitant costs in the resources of the measurement infrastructure. This motivates sampling of flow records.This paper addresses sampling strategy for flow records. Recent work has shown that non-uniform sampling is necessary in order to control estimation variance arising from the observed heavy-tailed distribution of flow lengths. However, while this approach controls estimator variance, it does not place hard limits on the number of flows sampled. Such limits are often required during arbitrary downstream sampling, resampling and aggregation operations employed in analysis of the data.This paper proposes a correlated sampling strategy that is able to select an arbitrarily small number of the "best" representatives of a set of flows. We show that usage estimates arising from such selection are unbiased, and show how to estimate their variance, both offline for modeling purposes, and online during the sampling itself. The selection algorithm can be implemented in a queue-like data structure in which memory usage is uniformly bounded during measurement. Finally, we compare the complexity and performance of our scheme with other potential approaches.

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a O(√n) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the shortest paths. This is optimal in a very strong sense. It is known that no compact routing using o(n) space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires Ω(√n) space per node.

It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space 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 give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from {0, …, N }, it approximates distances within a factor (1 + ε) in O (log log ( nN ) + 1/ε) time. Our scheme can be extended to find and route along correspondingly short dipaths.

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= 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 $\ensuremath{\text{\it OPT}}\ge \ensuremath{\text{\it LOAD}}$; previous work showed that $\ensuremath{\text{\it OPT}}\le 3\cdot 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 $\epsilon > 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 $\ensuremath{\text{\it OPT}}\geq L+c(h_{\max}/L)^{1/2+\epsilon}L$, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a $(2+\epsilon)$-approximation algorithm for the general case and polynomial-time approximation schemes for several natural special cases.

We present $\tilde{O}(m)$ time and space constant factor approximation algorithms for the k-median, k-center, and facility location problems with assignment costs being shortest path distances in a weighted undirected graph with n vertices and m edges. For all of these location problems, $\tilde{O}(n^2)$ time and space algorithms were already known, but here we are addressing large sparse graphs. An application could be placement of content distributing servers on the Internet. The Internet is large and changes so frequently that an $\tilde{O}(n^2)$ time solution would likely be outdated long before completion.

Traffic engineering and traffic matrix estimation are often treated as separate fields, even though one of the major applications for a traffic matrix is traffic engineering. In cases where a traffic matrix cannot be measured directly, it may still be estimated from indirect data (such as link measurements), but these estimates contain errors. Yet little thought has been given to the effects of inexact traffic estimates on traffic engineering. In this paper we consider how well traffic engineering works with estimated traffic matrices in the context of a specific task; namely that of optimizing network routing to minimize congestion, measured by maximum link-utilization. Our basic question is: how well is the real traffic routed if the routing is only optimized for an estimated traffic matrix? We compare against optimal routing of the real traffic using data derived from an operational tier-1 ISP. We find that the magnitude of errors in the traffic matrix estimate is not, in itself, a good indicator of the performance of that estimate in route optimization. Likewise, the optimal algorithm for traffic engineering given knowledge of the real traffic matrix is no longer the best with only the estimated traffic matrix as input. Our main practical finding is that the combination of a known traffic matrix estimation technique and a known traffic engineering technique can get close to the optimum in avoiding congestion for the real traffic. We even demonstrate stability in the sense that routing optimized on data from one day continued to perform well on subsequent days. This stability is crucial for the practical relevance to off-line traffic engineering, as it can be performed by ISPs today.

MPLS is becoming an important protocol for intradomain routing. MPLS routers are offered by the major vendors and many ISPs are deploying MPLS in their IP backbones, as well as in ATM and frame relay networks. For this period of possible transition to MPLS, it is urgent to increase our understanding of the power and limitation of MPLS. An attraction to MPLS is the flexibility it offers in engineering the routing of traffic in a network, e.g., to support higher demands without overloading any links. Mitra and Ramakrishnan [GLOBECOM'99] showed that optimal routing solutions may be found for a diverse set of traffic engineering goals. However, for a network with N nodes (routers) and M edges (links), their MPLS implementation may use /spl Omega/(N /spl times/ M) different labels. This is prohibitive since the number of labels is the number of entries needed in the router tables. We present an algorithm reducing the number of MPLS labels to N + M without increasing any link load. Our explicit N + M bound makes it easy to limit the table size requirement for a planned network, and the linearity allows for tables implemented in fast memory. For differentiated services with K traffic classes with different load constraints, our bound increases to K(N + M). Our stack-depth is only one, justifying implementations of MPLS with limited stack-depth.

Passive traffic measurement increasingly employs sampling at the packet level. Many high-end routers form flow statistics from a sampled substream of packets. Sampling is necessary in order to control the consumption of resources by the measurement operations. However, knowledge of the statistics of flows in the unsampled stream remains useful, for understanding both characteristics of source traffic, and consumption of resources in the network.This paper provide methods that use flow statistics formed from sampled packet stream to infer the absolute frequencies of lengths of flows in the unsampled stream. A key part of our work is inferring the numbers and lengths of flows of original traffic that evaded sampling altogether. We achieve this through statistical inference, and by exploiting protocol level detail reported in flow records. The method has applications to detection and characterization of network attacks: we show how to estimate, from sampled flow statistics, the number of compromised hosts that are sending attack traffic past the measurement point. We also investigate the impact on our results of different implementations of packet sampling.

We consider the performance of estimated tra#c matrices in tra#c engineering. More precisely, we first optimize the routing in an IP backbone to minimize congestion with the estimated tra#c matrix. We then test the performance of the resulting routing on the real tra#c matrix.

MPLS (MultiProtocol Label Switching) is a new technology proposed by the IETF [4,10] for network routing, and is being increasingly deployed by the largest Internet service providers. The MPLS technology differs from conventional network protocols in a crucial way: instead of reading the entire packet header at all switching points, the analysis of the packet header is done just once, when the packet header is assigned a stack of labels, and thenceforth, each switching point or router just gets to look at the label at the top of the stack (and the ingress edge), and based only on this information, it has to make a decision about the next-hop node [17,16]. In another departure from conventional routing and in particular from IP source routing, where the entire packet route is explicitly put in the header and popped off along the route, the router can not only pop the top label, it can push other labels on top of the stack.The two parameters of interest in designing MPLS routing protocols are the number of labels used, and the depth of the stack used for routing. Clearly, both cannot be simultaneously minimized, and there is often an interesting trade-off between label size and stack depth: it is obvious that if k labels are used, one must have a stack depth of logk n.In fact, it was not known whether this bound could be achieved even for trees; the best stack depth previously achieved with a constant number of labels was O(log2 n). In this paper, we show that one can indeed get asymptotically optimal upper bounds and route on trees using k labels and a maximum stack depth of O(logk n), and that this trade-off can be achieved using a simpler and more intuitive protocol than the one given in [9]. These tree-routing ideas are then shown to give better routing protocols for planar graphs as well. In particular, we show how to route along near-shortest paths (of length at most (1 + e) times the shortest-path) with O(log2 n/e) labels and logarithmic stack depth. We also apply them to graphs with smaller separators, including most large ISP networks.

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((hmax/L)1/7)L, where hmax is the maximum job height. Conversely, we prove that for any ε>0, there exists a c>0 such that for all sufficiently large integers hmax, there is a DYNAMIC STORAGE ALLOCATION instance with maximum job height hmax, maximum load at most L, and OPT≥ L+c(hmax/L)1/2+εL, for infinitely many integers L. En route, we construct several new polynomial-time approximation algorithms for DYNAMIC STORAGE ALLOCATION.

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.

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.

Abstract A balanced binary search tree can be characterized by two orthogonal issues: its search strategy and its balancing strategy. In this paper, we show how to decouple search and balancing strategies so that they can be expressed independently of each other, communicating only by basic operations such as rotations. Different balancing strategies, such as red–black trees and splay trees, and different search applications, such as key search and rank search, can be combined arbitrarily. As a new result, we show how optimal string search can be expressed as a search application on any balanced binary tree. We implement our framework in C++, with the heavy use of templates and inlining. It keeps balancing and searching separate, while still delivering a performance that compares favorably to widely used binary tree implementations. Common services, such as correctness checks and timing measurements, do not have to be rewritten for each tree implementation. The common framework simplifies experimentation with trees and search algorithms; as a demonstration, we present some simple comparisons of red–black trees, splay trees and treaps. Copyright © 2003 John Wiley & Sons, Ltd.

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.

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.

Many routers can generate and export statistics on flows of packets that traverse them. Increasingly, high end routers form flow statistics from only a sampled packet stream in order to manage resource consumption involved.This paper addresses three questions. Firstly: what are the downstream consequences for the measurement infrastructure? Long traffic flows will be split up if the time between sampled packets exceeds the flow timeout. Using packet header traces we show that flows generated by increasingly prevalent peer-to-peer applicalions are vulnerable to this effect.Secondly: can the volume of packet-sampled flow statistics be easily determined? We develop a simple model that predicts both the export rate of flow packet-sampled flow statistics and the number of active flows. It uses unsampled flow statistics---those commonly currently collected--as its data, i.e., it does not rely on having packet header traces available.Thirdly: what properties of the original traffic stream can be inferred from the packet sampled flow statistics? We show that as well as estimating total bytes and packets, one can also infer more detail, specifically the number and average length of flows in the unsampled traffic stream, even though some flows will have no packets sampled. We believe that this information is useful, both for understanding source traffic, e.g. the dependence of flow lengths on application type, and also monitoring changes in the composition of the traffic, e.g., a flood of short flows during a DoS attack. In all cases, we evaluate our approach using packet header traces gathered in backbone and campus networks.

A system of techniques is presented for optimizing open shortest path first (OSPF) or intermediate system-intermediate system (IS-IS) weights for intradomain routing in a changing world, the goal being to avoid overloaded links. We address predicted periodic changes in traffic as well as problems arising from link failures and emerging hot spots.

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.

We describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very small. The headers attached to the routed messages, including the name of the destination, are extremely short. The routing decision at each node takes constant time. Yet, the stretch of these routing schemes, i.e., the worst ratio between the cost of the path on which a packet is routed and the cost of the cheapest path from source to destination, is a small constant. Our schemes achieve a near-optimal tradeoff between the size of the routing tables used and the resulting stretch. More specifically, we obtain:

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.

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.}

Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O (log 2 n ) for connectivity, O (log 4 n ) for minimum spanning forest, 2-edge connectivity, and O (log 5 n ) biconnectivity.

Open shortest path first (OSPF) is the most commonly used intra-domain Internet routing protocol. Traffic flow is routed along shortest paths, splitting flow at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to their physical distances, but often the main goal is to avoid congestion, i.e., overloading of links, and the standard heuristic recommended by Cisco is to make the weight of a link inversely proportional to its capacity. Our starting point was a proposed AT&T WorldNet backbone with demands projected from previous measurements. The desire was to optimize the weight setting based on the projected demands. We showed that optimizing the weight settings for a given set of demands is NP-hard, so we resorted to a local search heuristic. Surprisingly it turned out that for the proposed AT&T WorldNet backbone, we found weight settings that performed within a few percent from that of the optimal general routing where the flow for each demand is optimally distributed over all paths between source and destination. This contrasts the common belief that OSPF routing leads to congestion and it shows that for the network and demand matrix studied we cannot get a substantially better load balancing by switching to the proposed more flexible multi-protocol label switching (MPLS) technologies. Our techniques were also tested on synthetic internetworks, based on a model of Zegura et al., (1996), for which we did not always get quite as close to the optimal general routing.

We introduce a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. Based on this we present optimal bounds for ...

Article Free Access Share on Near-optimal fully-dynamic graph connectivity Author: Mikkel Thorup AT&T Labs--Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ AT&T Labs--Research, Shannon Laboratory, 180 Park Avenue, Florham Park, NJView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 343–350https://doi.org/10.1145/335305.335345Published:01 May 2000Publication History 121citation2,192DownloadsMetricsTotal Citations121Total Downloads2,192Last 12 Months234Last 6 weeks88 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The maximum agreement subtree problem is the following. Given two rooted trees whose leaves are drawn from the same set of items (e.g., species), find the largest subset of these items so that the portions of the two trees restricted to these items are isomorphic. We consider the case which occurs frequently in practice, i.e., the case when the trees are binary, and give an O(nlog n) time algorithm for this problem.

Priority queues are some of the most fundamental data structures. For example, they are used directly for task scheduling in operating systems. Moreover, they are essential to greedy algorithms. We study the complexity of integer priority queue operations on a RAM with arbitrary word size, modeling the possibilities in standard imperative programming languages such as C. We present exponential improvements over previous bounds, and we show tight relations to sorting. Our first result is a RAM priority queue supporting find-min in constant time and insert and delete-min in time O(log log n), where n is the current number of keys in the queue. This is an exponential improvement over the $O(\sqrt{\log n})$ bound of Fredman and Willard [ Proceedings of the 22nd ACM Symposium on the Theory of Computing, Baltimore, MD, pp. 1--7]. Plugging this priority queue into Dijkstra's algorithm gives an O(mlog log m) algorithm for the single source shortest path problem on a graph with m edges, as compared with the previous $O(m\sqrt{\log m})$ bound based on Fredman and Willard's priority queue. The above bounds assume $O(n 2^{{\varepsilon} w})$ space, where w is the word length and ${\varepsilon}>0$. They can, however, be achieved in linear space using randomized hashing. Our second result is a general equivalence between sorting and priority queues. A priority queue is monotone if the minimum is nondecreasing over time, as in many greedy algorithms. We show that on a RAM, the amortized operation cost of a monotone priority queue is equivalent to the per-key cost of sorting. For example, the equivalence implies that the single source shortest paths problem on a graph with m edges is no harder than that of sorting m keys. With the current RAM sorting, this gives an O(m log log m) time bound, as above, but the relation holds regardless of the future developments in RAM sorting. From the equivalence result, for any fixed ${\varepsilon}>0$, we derive a randomized monotone $O(\sqrt{\log n}^{1+{\varepsilon}})$ priority queue with expected constant time decrease-key. Plugging this into Dijkstra's algorithm gives an $O(n\sqrt{\log n}^{1+{\varepsilon}}+m)$ algorithm for the single source shortest path problem on a graph with n nodes and m edges, complementing the above O(mlog log m) algorithm if $m\gg n$. This improves the O(nlog n/log log n + m) bound by Fredman and Willard [Proceedings of the 31st IEEE Symposium on the Foundations of Computer Science, St. Louis, MO, 1990, pp. 719--725], based on their O(log n/log log n) priority queue with constant decrease-key.

Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The multiway cut problem is to find a minimum-cost multiway cut. This problem is Max-SNP hard. Recently Calinescu, Karloff, and Rabani (STOC'98) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (3=2 1=k)-approximation algorithm. In this paper, we study their geometric relaxation. In particular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). For k = 3, we show the integrality gap is 12=11, giving tight upper and lower bounds. That is, we exhibit a graph with integrality gap 12=11 and give an algorithm that finds a cut of value 12=11 times the relaxation value. This is the best possible performance guarantee for any algorithm based purely on the value of the relaxation and improves on Calinescu et al.'s factor of 7/6. We also improve the upper bounds for all larger values of k. For k = 4; 5, our best upper bounds are based on computer constructed and analyzed rounding schemes, while for k > 6 we give an algorithm with performance ratio 1:3438 k . Our results were discovered with the help of computational experiments that we also describe here. MIT Laboratory for Computer Science, Cambridge, MA 02138. [email protected]. Research supported by NSF contract CCR9624239, an Alfred P. Sloane Foundation Fellowship, and a David and Lucille Packard Foundation Fellowship. y Brown University . [email protected]. Research supported by NSF Grant CCR-9700146. z Dartmouth College. [email protected]. Research supported by NSF Caree...

The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively 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 for general directed and undirected graphs 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 positive integer weights. The algorithm avoids the sorting bottleneck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.

We consider the problem of fitting an n × n distance matrix D by a tree metric T. Let $\varepsilon$ be the distance to the closest tree metric under the $L_{\infty}$ norm; that is, $\varepsilon=\min_T\{\parallel T-D\parallel{\infty}\}$. First we present an O(n 2 ) algorithm for finding a tree metric T such that $\parallel T-D\parallel{\infty}\leq 3\varepsilon$. Second we show that it is ${\cal NP}$-hard to find a tree metric T such that $\parallel T-D\parallel{\infty} < \frac{9}{8}\varepsilon$. This paper presents the first algorithm for this problem with a performance guarantee.

A linear-time algorithm is presented for finding dominators in control flow graphs.

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.

Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning forest, a-edge connectivity, and biconnectivity.Assuming that we start with no edges in a graph with n vertices, the amortized operation cost0 arc O(log2 n) for connectivity and O(log4 n) for minimum spanning forest, 2+dgeconnectivity, and biconnectity.

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.

Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in use. Current practice dictates that trees be constructed using different methods and that the resulting trees should be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study one formalization of the problem: the maximum agreement-subtree $($\MAST$)$ problem. The $\MAST$ problem is as follows: given a set A and two rooted trees $\cT_0$ and $\cT_1$ leaf-labeled by the elements of A, find a maximum-cardinality subset B of A such that the topological restrictions of $\cT_0$ and $\cT_1$ to B are isomorphic. In this paper, we will show that this problem reduces to unary weighted bipartite matching ($\UWBM$) with an $O(n^{1+o(1)})$ additive overhead. We also show that $\UWBM$ reduces linearly to $\MAST$. Thus our algorithm is optimal unless $\UWBM$ can be solved in near linear time. The overall running time of our algorithm is $O(n^{1.5} \log n)$, improving on the previous best algorithm, which runs in $O(n^2)$. We also derive an $O(n c^{\sqrt{\log n}})$-time algorithm for the case of bounded degrees, whereas the previously best algorithm runs in $O(n^2),$ as in the unbounded case.

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).

String matchingand Compression are two widely studied areas of computer science.The theory of

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/).>

A new approach to ambiguity of context-free grammars is presented, and within this approach the LL and LR techniques are generalized to solve the following problems for large classes of ambiguous grammars: The user may control the parser generation so as to get a parser which finds some specific parse trees for the sentences. The generalized LL and LR techniques will still guarantee that the resulting parser accepts all sentences and terminates in linear time on all input.