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

We consider the hash function $h(x) = ((ax+b)mod p)mod n$ where $a,b$ are chosen uniformly at random from $\{0,1,\ldots,p-1\}$. We prove that when we use $h(x)$ in hashing with chaining to insert $n$ elements into a table of size $n$ the expected length of the longest chain is $\tilde{O}\!\left(n^{1/3}\right)$. The proof also generalizes to give the same bound when we use the multiply-shift hash function by Dietzfelbinger et al. [ J. Algorithms, 25 (1997), pp. 19--51].

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.

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.

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.

A graph U is an induced universal graph for a family F of graphs if every graph in F is a vertex-induced subgraph of U. We give upper and lower bounds for the size of induced universal graphs for the family of graphs with n vertices of maximum degree D. Our new bounds improve several previous results except for the special cases where D is either near-constant or almost n/2. For constant even D Butler [Graphs and Combinatorics 2009] has shown O(n^(D/2)) and recently Alon and Nenadov [SODA 2017] showed the same bound for constant odd D. For constant D Butler also gave a matching lower bound. For generals graphs, which corresponds to D = n, Alon [Geometric and Functional Analysis, to appear] proved the existence of an induced universal graph with (1+o(1)) \cdot 2^((n-1)/2) vertices, leading to a smaller constant than in the previously best known bound of 16 * 2^(n/2) by Alstrup, Kaplan, Thorup, and Zwick [STOC 2015]. In this paper we give the following lower and upper bound of binom(floor(n/2))(floor(D/2)) * n^(-O(1)) and binom(floor(n/2))(floor(D/2)) * 2^(O(sqrt(D log D) * log(n/D))), respectively, where the upper bound is the main contribution. The proof that it is an induced universal graph relies on a randomized argument. We also give a deterministic upper bound of O(n^k / (k-1)!). These upper bounds are the best known when D <= n/2 - tilde-Omega(n^(3/4)) and either D is even and D = omega(1) or D is odd and D = omega(log n/log log n). In this range we improve asymptotically on the previous best known results by Butler [Graphs and Combinatorics 2009], Esperet, Arnaud and Ochem [IPL 2008], Adjiashvili and Rotbart [ICALP 2014], Alon and Nenadov [SODA 2017], and Alon [Geometric and Functional Analysis, to appear].

Let $G$ be an unweighted, undirected graph. An additive $k$-spanner of $G$ is a subgraph $H$ that approximates all distances between pairs of nodes up to an additive error of $+k$, that is, it satisfies $d_H(u,v) \le d_G(u,v)+k$ for all nodes $u,v$, where $d$ is the shortest path distance. We give a deterministic algorithm that constructs an additive $O\!\left(1\right)$-spanner with $O\!\left(n^{4/3}\right)$ edges in $O\!\left(n^2\right)$ time. This should be compared with the randomized Monte Carlo algorithm by Woodruff [ICALP 2010] giving an additive $6$-spanner with $O\!\left(n^{4/3}\log^3 n\right)$ edges in expected time $O\!\left(n^2\log^2 n\right)$. An $(α,β)$-approximate distance oracle for $G$ is a data structure that supports the following distance queries between pairs of nodes in $G$. Given two nodes $u$, $v$ it can in constant time compute a distance estimate $\tilde{d}$ that satisfies $d \le \tilde{d} \le αd + β$ where $d$ is the distance between $u$ and $v$ in $G$. Sommer [ICALP 2016] gave a randomized Monte Carlo $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\text{poly} \log n\right)$ in expected time $O\!\left(n^2\text{poly} \log n\right)$. As an application of the additive $O(1)$-spanner we improve the construction by Sommer [ICALP 2016] and give a Las Vegas $(2,1)$-distance oracle of size $O\!\left(n^{5/3}\right)$ in time $O\!\left(n^2\right)$. This also implies an algorithm that in $O\!\left(n^2\right)$ gives approximate distance for all pairs of nodes in $G$ improving on the $O\!\left(n^2 \log n\right)$ algorithm by Baswana and Kavitha [SICOMP 2010].

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.

Finding cycles in graphs is a fundamental problem in algorithmic graph theory. In this paper, we consider the problem of finding and reporting a cycle of length 2k in an undirected graph G with n nodes and m edges for constant k≥ 2. A classic result by Bondy and Simonovits [J. Combinatorial Theory, 1974] implies that if m ≥ 100k n1+1/k, then G contains a 2k-cycle, further implying that one needs to consider only graphs with m = O(n1+1/k).

In this article, we show that there exists a graph G with O ( n ) nodes such that any forest of n nodes is an induced subgraph of G . Furthermore, for constant arboricity k , the result implies the existence of a graph with O ( n k ) nodes that contains all n -node graphs of arboricity k as node-induced subgraphs, matching a Ω ( n k ) lower bound of Alstrup and Rauhe. Our upper bounds are obtained through a log 2 n + O (1) labeling scheme for adjacency queries in forests. We hereby solve an open problem being raised repeatedly over decades by authors such as Kannan et al., Chung, and Fraigniaud and Korman.

A distance labeling scheme labels the n nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the two nodes by looking only at the labels. A D-preserving distance labeling scheme only returns precise distances between pairs of nodes that are at distance at least D from each other. In this paper we consider distance labeling schemes for the classical case of unweighted and undirected graphs. We present a O(n/D * log^2(D)) bit D-preserving distance labeling scheme, improving the previous bound by Bollobás et al. [SIAM J. Discrete Math. 2005]. We also give an almost matching lower bound of Omega(n/D). With our D-preserving distance labeling scheme as a building block, we additionally achieve the following results: 1. We present the first distance labeling scheme of size o(n) for sparse graphs (and hence bounded degree graphs). This addresses an open problem by Gavoille et. al. [J. Algo. 2004], hereby separating the complexity from distance labeling in general graphs which require Omega(n) bits, Moon [Proc. of Glasgow Math. Association 1965]. 2. For approximate r-additive labeling schemes, that return distances within an additive error of r we show a scheme of size O(n/r * polylog(r*log(n))/log(n)) for r >= 2. This improves on the current best bound of O(n/r) by Alstrup et al. [SODA 2016] for sub-polynomial r, and is a generalization of a result by Gawrychowski et al. [arXiv preprint 2015] who showed this for r=2.

The most classic textbook hash function, e.g. taught in CLRS [MIT Press'09], is h(x) = ((ax + b) mod p) mod m, (◊) where x, a, b ε {0, 1, …, p –} and a, b are chosen uniformly at random. It is known that (◊) is 2-independent and almost uniform provided p is a prime and p » m. This implies that when using (◊) to build a hash table with chaining that contains n ≤ m keys, the expected query time is O(1) and the expected length of the longest chain is O(√n). This result holds for any 2-independent hash function. No hash function can improve on the expected query time, but the upper bound on the expected length of the longest chain is not known to be tight for (◊). Partially addressing this problem, Alon et al. [STOC'97] proved the existence of a class of linear hash functions such that the expected length of the longest chain is (√n) and leave as an open problem to decide which nontrivial properties (◊) has. We make the first progress on this fundamental problem, by showing that the expected length of the longest chain is at most n1/3o(1) which means that the performance of (◊) is similar to that of a 3-independent hash function for which we can prove an upper bound of O(n1/3). As a lemma we show that within a fixed set of integers there are few pairs such that the height of the ratio of the pairs are small. Given two non-zero coprime integers n, m ε Z with the height of n/m is max t{|n|, |m|}, and the height is a way of measuring how complex a fraction is. This is proved using a mixture of techniques from additive combinatorics and number theory, and we believe that the result might be of independent interest. For a natural variation of (◊), we show that it is possible to apply second order moment bounds even when a hash value is fixed. As a consequence: For min-wise hashing it was known that any key from a set of n keys has the smallest hash value with probability O (1√n). We improve this to n–1+o(1). For linear probing it was known that the worst case expected query time is O (√n). We improve this to no(1).

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.

We show that there exists a graph G with O(n) nodes, where any forest of n nodes is a node-induced sub graph of G. Furthermore, for constant arboricity k, the result implies the existence of a graph with O(nk) nodes that contains all n-node graphs as node-induced sub graphs, matching a Ω(nk) lower bound. The lower bound and previously best upper bounds were presented in Alstrup and Rauhe (FOCS'02). Our upper bounds are obtained through a log2(n) + O(1) labeling scheme for adjacency queries in forests. We hereby solve an open problem being raised repeatedly over decades, e.g. In Kannan, Naor, Rudich (STOC 1988), Chung (J. Of Graph Theory 1990), Fraigniaud and Korman (SODA 2010).

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.