BRICS RS-97-16 Alon et al.: Linear Hashing BRICS

Basic Research in Computer Science

Linear Hashing

Noga Alon Martin Dietzfelbinger Peter Bro Miltersen Erez Petrank Gábor Tardos

BRICS Report Series RS-97-16

ISSN 0909-0878 June 1997 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1997, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/97/16/

Linear Hashing

Noga Alon^{∗} Martin Dietzfelbinger^{†} Peter Bro Miltersen^{‡}
Erez Petrank^{§}  Gábor Tardos^{¶}

Abstract

Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good H is as a class of hash functions, namely we consider hashing a set S of size n into a range having the same cardinality n by a randomly chosen function from H and look at the expected size of the largest hash bucket. H is a universal class of hash functions for any finite field, but with respect to our measure different fields behave differently.

∗Dep. of Math., Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel and Institute for Advanced Study, Princeton, NJ 08540. Research supported in part by a USA-Israeli BSF grant, by the Sloan Foundation grant No. 96-6-2, by an NEC Research Institute grant and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv

University. E-mail: noga@math.tau.ac.il.

†Fachbereich Informatik, Lehrstuhl II, Universität Dortmund, D-44221 Dortmund, Ger-

many. E-mail: dietzf@ls2.informatik.uni-dortmund.de. Partially supported by DFG

grant Di 412/5-1.

‡BRICS, Centre of the Danish National Research Foundation, University of Aarhus, Ny Munkegade, Aarhus, Denmark. Supported by the ESPRIT Long Term Research Programme of the EU under project number 20244 (ALCOM-IT). E-mail: bromille@brics.dk. Part of this work was done while the author was at the University of Toronto.

§DIMACS, P.O.Box 1179, Piscataway, NJ 08855-1179, USA. E-mail: erez@dimacs.rutgers.edu. Part of this work was done while the author was visiting the University of Toronto.

¶Mathematical Institute of the Hungarian Academy of Sciences, Pf. 127, Budapest, H-1364 Hungary. Supported by NSF grants CCR-95-03254 and DMS-9304580, a grant from Fuji Bank and the grant OTKA-F014919. E-mail: tardos@cs.elte.hu. Part of this work was done while the author was visiting the University of Toronto and the Institute for Advanced Study, Princeton.

If the finite field F has n elements then there is a bad set S ⊂ F^{2} of size n with expected maximal bucket size Ω(n^{1/3}). If n is a perfect square then there is even a bad set with largest bucket size always at least \sqrt{n}. (This is worst possible, since with respect to a universal class of hash functions every set of size n has expected largest bucket size below \sqrt{n} + 1/2.)

If, however, we consider the field of two elements then we get much better bounds. The best previously known upper bound on the expected size of the largest bucket for this class was O(2^{\sqrt{log n}}). We reduce this upper bound to O(log n log log n). Note that this is not far from the guarantee for a random function. There, the average largest bucket would be Θ(log n/ log log n).

In the course of our proof we develop a tool which may be of independent interest. Suppose we have a subset S of a vector space D over Z_{2}, and consider a random linear mapping of D to a smaller vector space R. If the cardinality of S is larger than c_{ϵ}|R| log |R| then with probability 1 − ϵ, the image of S will cover all elements in the range.

1 Introduction

Consider distributing n balls in s buckets, randomly and independently. The resulting distribution of the balls in the buckets is the object of occupancy theory.

In the theory of algorithms and in complexity theory, it is often necessary and useful to consider putting balls in buckets without complete independence. More precisely, the following setting is studied: A class H of hash functions, each mapping a universe U to {1, 2, …, s}, is fixed. A set S ⊆ U to be hashed is given by an adversary, a member h ∈ H is chosen uniformly at random, S is hashed using h, and the distribution of the multi-set {h(x)|x ∈ S} is studied. If the class H is the class of all functions between U and {1, 2, …, s}, we get the classical occupancy problems. Carter and Wegman defined a class H to be universal if^{1}

∀x ≠ y ∈ U : Prob(h(x) = h(y)) ≤ 1/s.

1We remark that a stricter definition is often used in the complexity theory literature, and a more liberal definition is often used in the data structure literature.

For universal families, the following properties are well known; variations of them have been used extensively in various settings:

1. If S of size n is hashed to n^{2} buckets, with probability more than 1/2, no collision occurs.

2. If S of size 2n^{2} is hashed to n buckets, with probability more than 1/2, every bucket receives an element.

3. If S of size n is hashed to n buckets, the expected size of the largest bucket is less than \sqrt{n} + \frac{1}{2}.

The intuition behind universal hashing is that we often lose relatively little compared to using a completely random map. Note that for the property 1, this is true in a very strong sense; even with complete randomness, we do not expect o(n^{2}) buckets to suffice (the birthday paradox), so nothing is lost by using a universal family instead. The bounds in the second and third properties, however, are rather coarse-grained compared to what one would get with complete randomness. For property 2, with complete randomness, Θ(n log n) balls would suffice to cover the buckets with good probability (the coupon collector’s theorem), i.e. a polynomial improvement over n^{2}, and for property 3, with complete randomness, we expect the largest bucket to have size Θ(log n/ log log n), i.e. an exponential improvement over \sqrt{n}. In these last cases we do seem to loose quite a lot compared to using a completely random map and better bounds would seem desirable. However, it is rather easy to construct (unnatural) families of universal families and sets to be hashed showing that size Θ(n^{2}) is necessary to cover n buckets with non-zero probability, and that buckets of size \sqrt{n} are, in general unavoidable, when a set of size n is hashed to n buckets. This shows that the abstract property of universality does not allow for stronger statements. Now fix a concrete universal family of hash functions. We ask the following question: To which extent are the fine-grained occupancy properties of completely random maps preserved?

We provide answers to these questions for the case of linear maps between two vector spaces over a finite field, a natural and well known class of universal hash functions. The general flavor of our results is that “large fields are bad”, in the sense that the bounds becomes the worst possible for universal families, while “small fields are good” in the sense that the bounds become as good or almost as good as the ones for independently distributed balls.

More precisely, for the covering problem, we show the following (easy) theorem

Theorem 1 Let F be a field of size n and let H be the class of linear maps between F^{2} and F. There is a subset S of F^{2} of size Θ(|F |^{2}), so that for no h ∈ H, h(S) = F.

On the other hand, we prove the following harder theorem

Theorem 2 Let S be a subset of a vector space over Z_{2} and choose a random linear map to a smaller vector space R. If |S| ≥ c_{ϵ}|R| log |R| then with probability at least 1 − ϵ the image of S covers the entire range R.

For the “largest bucket problem”, let us first introduce some notation: Let U be the universe from which the keys are chosen. We fix a class H mapping U to {1, …, s}. Then, a set S ⊆ U of size n is chosen by an adversary, and we uniformly at random pick a hash function h ∈ H, hash S using h and look at the size of the largest resulting hash bucket. We denote the expectation of this size by L_{n}^{s}. Formally,

L_{n}^{s}(H) = max_{S⊆U,|S|=n} E_{h∈H}[ max_{y∈{1,...,s}} |{x ∈ S | h(x) = y}|]

Usually we think of s being of size close to n. Note that if s = Ω(n^{2}), any universal class yields L_{n}^{s} = O(1).

The class H we will consider is the set of linear maps between F^{m} → F^{k} for m > k. Here F is a finite field and s = |F |^{k}. This class is universal for all values of the parameters.

When k = 1 and thus |F | = s the expected largest bucket can be large.

Theorem 3 Let F be a finite field with |F | = s. For the class H of all linear transformations F^{2} → F we have

L_{s}^{s}(H) = Ω(s^{1/3}).

Furthermore if |F | is a perfect square we have

L_{s}^{s}(H) > \sqrt{s}.

Note how close our lower bound for quadratic fields is to the upper bound of \sqrt{s} + 1/2 that holds for every universal class. We also mention that for the bad set we construct in Theorem 8 for a quadratic field there is no good hash function, since there always exists a bucket of size at least \sqrt{s}.

When the field is the field of two elements, the situation is completely different. Markowsky, Carter and Wegman [MCW78] showed that for this case L_{s}^{s}(H) = O(s^{1/4}). Mehlhorn and Vishkin [MV84] improved on this result (although this is implicit in their paper) and showed that L_{s}^{s}(H) = O(2^{\sqrt{log s}}). We further improve the bound and show that:

Theorem 4 For the class H of all linear transformations between two vector spaces over Z_{2},

L_{s}^{s}(H) = O(log s log log s).

Furthermore, we also show that even if the range is smaller than |S| by a logarithmic factor, the same still holds:

Theorem 5 For the class H of all linear transformations between two vector spaces over Z_{2},

L_{s log s}^{s}(H) = O(log s log log s).

Note that even if one uses the class R of all functions one obtains only a slightly better result: the expected size of the largest bucket in this case is L_{s}^{s}(R) = Θ(log s/ log log s) and L_{s log s}^{s}(R) = Θ(log s), which is the best possible bound for any class. Interestingly, our upper bound is based on our upper bound for the covering property.

We do not know what the right bound is for the class of linear maps over Z_{2}, i.e., is it as good as O(log s/ log log s)? We leave this as an open question.

1.1 Motivation

There is no doubt that the method of implementing a dictionary by hashing with chaining, recommended in textbooks [CLR90, GBY90] especially for situations with many update operations, is a practically important scheme.

In situations in which a good bound on the cost of single operations is important, e. g., in real-time applications, the expected maximal bucket size as formed by all keys ever present in the dictionary during a time interval plays a crucial role. Our results show that, at least as long as the size of the hash table can be determined right at the start, using a hash family of linear functions over Z_{2} will perform very well in this respect. For other simple hash classes such bounds on the worst case bucket size are not available or are even wrong (see Theorem 8); other, more sophisticated hash families [S89, DM90, DGMP92] that do guarantee small maximal bucket sizes consist of functions with higher evaluation time. Of course, if worst case constant time for certain operations is absolutely necessary, the known two-level hashing schemes can be used, e. g., the FKS scheme [FKS84] for static dictionaries; dynamic perfect hashing [DKMHRT94] for the dynamic case with constant time lookups and expected time O(n) for n update operations; and the “realtime dictionaries” from [DM90] that perform each operation in constant time, with high probability. It should be noted, however, that a price is to be paid for the guaranteed constant lookup time in the dynamic schemes: the (average) cost of insertions is significantly higher than in simple schemes like chained hashing; the overall storage requirements are higher as well.

1.2 Related work

Another direction in trying to show that a specific class has a good bound on the expected size of the largest bucket is to build a class specifically designed to have such good property.

One immediate such result is obtained by looking at the class of d-degree polynomials over finite fields, where d = c log n/ log log n (see, e.g., [ABI86].) It is easy to see that this class maps each d elements of the domain independently to the range, and thus, the bound that applies to the class of all functions also applies to this class. We can combine this with the following well known construction, (which is usually called “collapsing the universe”) : At the expense of Θ(log n + log log |U|) random bits one can construct a map g : U → {1, …, n^{k+2}} that on any set S will be one-to-one with probability 1 − O(1/n^{k}). This gives us a class with L_{n}^{n} = Θ(log n/ log log n) of size 2^{O(log log |U|+log^{2} n/ log log n)} and with evaluation time O(log n/ log log n) in a reasonable model of computation, say, a RAM with unit cost operations on members of the universe to be hashed.

More efficient (but much larger) families where given by Siegel [S89] and by Dietzfelbinger and Meyer auf der Heide [DM90]. Both provide families of size |U|^{n^{ϵ}} such that the functions can be evaluated in O(1) time on a RAM and with L_{n}^{n} = Θ(log n/ log log n). The families from [S89] and [DM90] are somewhat complex to implement while the class of linear maps requires only very basic bit operations (as discussed already in [CW79]). It is therefore desirable to study this class, and this is the main purpose of the present paper.

1.3 Notation

If S is a subset of the domain D of a function h we use h(S) to denote {h(s) | s ∈ S}. If x is an element of the range we use h^{−1}(x) to denote {s ∈ D | h(s) = x}. If A and B are subsets of a vector space V and x ∈ V we use the notations A+B = {a+b | a ∈ A∧b ∈ B} and x+A = {x+a | a ∈ A}. We use Z_{2} to denote the two element field. All logarithms in this paper are base two.

2 The covering property

2.1 Lower bounds for covering with a large field

We prove Theorem 1. Take a set A ⊂ F of size |A| = ⌊|F |/2⌋ and consider S = {(x, y) | y ≠ 0 ∧ x/y ∈ A ∧ (x − 1)/y ∉ A}. S has density around one quarter and no linear map g : F^{2} → F satisfies g(S) = F. To see this take a nonzero linear map g : (x, y) ↦ ax + by and note that if 0 ∈ g(S) then a ≠ 0 and −b/a ∈ A but in this case a ∉ g(S).

2.2 Upper bounds for covering with a small field - the existential case

We start by showing that if we have a large enough subset A of a vector space over Z_{2} then there exists a linear transformation T to a large vector space such that T (A) is the entire range. The constant e below is the base of the natural logarithm.

Theorem 6 Let A be a finite set of vectors in a vector space V of an arbitrary dimension over Z_{2} and let t > 0 be an integer. If |A| > t2^{t}/ log e then there exists a linear map T : V → Z_{2}^{t}, so that T maps A onto Z_{2}^{t}.

For the proof of this theorem we need the following simple lemma. Note that although we state the lemma for vector spaces, it holds for any finite group.

Lemma 2.1 Let V be a finite vector space, A ⊆ V, α = 1 − |A|/|V |. Then for a random v ∈ V it holds that

E_{v}(1 − |A ∪ (v + A)|/|V |) = α^{2}.

Proof. If v and u are both chosen uniformly independently at random from V then both events u ∉ A and u ∉ v + A have probability α and they are independent. □ Proof of Theorem 6. Let m be the dimension of V, N = |A| and α = 1 − |A|/|V | = 1 − N/2^{m}. Starting with A_{0} = A, we choose a vector v_{1} ∈ V so that for A_{1} = A_{0} ∪ (v_{1} + A_{0})

1 − \frac{|A_{1}|}{|V |} ≤ α^{2}.

Such a choice for v_{1} exists by Lemma 2.1. Then, by the same procedure, we choose a v_{2} so that for

A_{2} = A_{1} ∪ (v_{2} + A_{1}) = A + Span{v_{1}, v_{2}},

1 − \frac{|A_{2}|}{|V |} ≤ α^{4},

and so on up to A_{s} = A + Span{v_{1}, …, v_{s}} with s = m − t for which

1 − \frac{|A_{s}|}{|V |} ≤ α^{2^{s}}.

Note that one can assume that the vectors v_{1}, …, v_{s} are linearly independent since choosing a vector v_{i} which depends on the previous choices makes A_{i} = A_{i−1}.

We now claim that A_{s} = V. Suppose in way of contradiction that A_{s} ≠ V. Take a vector v ∈ V outside A_{s}, then v + Span{v_{1}, …, v_{s}} is disjoint from A_{s}; thus

1 − \frac{|A_{s}|}{|V |} ≥ 2^{s}/2^{m}.

Combining the last two inequalities and recalling that t = m − s we get

2^{−t} ≤ α^{2^{s}} = (1 − N/2^{m})^{2^{s}} < e^{−N2^{−t}}.

Taking the logarithm of both sides yields −t < −N log_{2} e/2^{t} contradicting our assumption on N. Thus, A_{s} = V must hold.

Now we choose a linear map T : V → Z_{2}^{t} such that its kernel T^{−1}(0) = Span{v_{1}, …, v_{s}}. The equality V = A_{s} = A + Span{v_{1}, …, v_{s}} implies that T maps A onto Z_{2}^{t}. □

The bound in Theorem 6 is asymptotically tight as shown by the following proposition.

Proposition 2.2 For every large enough integer t there is a set A of at least (t − 3 log t)2^{t}/ log e vectors in a vector space V over Z_{2} so that for any linear map T : V → Z_{2}^{t}, T does not map A onto Z_{2}^{t}.

Proof: Let V = Z_{2}^{t+s} with s = ⌊t/10⌋ and let A be chosen at random by picking each element of V independently and with probability p = 1 − 2^{−x} into the set with x = (t − 2 log t)2^{−s}. From Chebyshev’s inequality we know that with probability at least 3/4, A has cardinality at least pN − 2\sqrt{pN} for N = 2^{s+t}. Using p > x/ log e − x^{2}/(2 log^{2} e) one can show that this is as many as claimed in the proposition. Let us compute the probability that there exists a linear map T : V → Z_{2}^{t} such that T maps A onto Z_{2}^{t}. There are 2^{t(t+s)} possible maps T and each of them satisfies T (A) = Z_{2}^{t} with

probability at most (1 − (1 − p)^{2^{s}})^{2^{t}} = (1 − 2^{−2^{s}x})^{2^{t}} = (1 − t^{2}/2^{t})^{2^{t}} < e^{−t^{2}}. So with probability almost 3/4, A is not small and still no T maps A onto Z_{2}^{t}. □

2.3 Choosing the linear map at random

In this subsection we strengthen Theorem 6 and prove that if A is bigger than what is required there by only a constant factor, then almost all choices of the linear transformation T work. This may seem immediate at first glance since Lemma 2.1 tells us that a random choice for the next vector is good on average. In particular, it might seem that for a random choice of v_{1} and v_{2} in the proof of Theorem 6, E_{v_{1},v_{2}}(1 − |A + Span{v_{1}, v_{2}}|/|V |) ≤ α^{4}. Unfortunately this is not the case: For example, think of A being a linear subspace containing half of V. In this case, the ratio α of points that are not covered is 1/2. As random vectors v_{i} are chosen to be added to A, vectors in A are chosen with probability 1/2. Thus, after i steps, α remains 1/2 with probability 1/2^{i} and becomes 0 otherwise. Thus, the expected value of α_{i} is 2^{−i−1} which is much bigger than 2^{−2^{i}}.

Our first lemma is technical in nature.

Lemma 2.3 Let α_{i} for 1 ≤ i ≤ k be random variables and let 0 < α_{0} < 1 be a constant. Suppose that for 0 ≤ i < k we have 0 ≤ α_{i+1} ≤ α_{i} and conditioned on any set of values for α_{1}, …, α_{i} we have E[α_{i+1}|α_{1}, …, α_{i}] = α_{i}^{2}. Then for any threshold 0 < t < 1 we have

Prob[α_{k} ≥ t] ≤ α_{0}^{k−log log(1/t)+log log(1/α_{0})}.

Proof: The proof is by induction on k. The k = 0 base case is trivial.

We assume the statement of the lemma is true for k and prove it for k +1. Let c = k − log log(1/t). We may suppose c + 1 + log log(1/α_{0}) ≥ 0 since otherwise the bound in the lemma is above 1.

After the choice of α_{1}, the rest of the random variables form a random process of length k satisfying the conditions of the lemma (unless α_{1} = 0); thus we can apply the inductive hypothesis to get

Prob[α_{k+1} ≥ t] = E_{α_{1}}[Prob[α_{k+1} ≥ t | α_{1}]] ≤ E[f(α_{1})],

where we define f_{0}(x) = x^{c+log log(1/x)} for 0 < x < 1 and take f(x) = min(1, f_{0}(x)) in the same interval and f(0) = 0. The value f(α_{1}) is clearly an upper bound on Prob[α_{k+1} ≥ t | α_{1}].

We claim that in the interval 0 ≤ x ≤ α_{0} we have f(x) ≤ f_{0}(α_{0})x/α_{0}. To prove this simply observe that f_{0}(x)/x is first increasing then decreasing on (0, 1). To see this compute the derivative (f_{0}(x)/x)′ = (c + log e − 1 + log log(1/x))f_{0}(x)/x^{2}. If α_{0} is still in the increasing phase then we have f(x)/x ≤ f_{0}(x)/x ≤ f_{0}(α_{0})/α_{0} for 0 < x ≤ α_{0}. Suppose now that α_{0} is already in the decreasing phase and define x′ = 2^{−2^{−c−1}}. Notice that we assumed α_{0} ≤ x′ in the beginning of the proof, so we have f_{0}(α_{0})/α_{0} ≥ f_{0}(x′)/x′. Let us define x′′ = x^{′2} = 2^{−2^{−c}} and notice that we have f(x) = 1 if and only if x ≥ x′′. It is easy to check that x′′ must still be in the increasing phase of f_{0}(x)/x thus we have f(x)/x = f_{0}(x)/x ≤ f_{0}(x′′)/x′′ = 1/x′′ for 0 < x ≤ x′′. For x′′ ≤ x < 1 we simply have f(x)/x = 1/x ≤ 1/x′′. Thus we must have f(x)/x ≤ 1/x′′ = f_{0}(x′)/x′ ≤ f_{0}(α_{0})/α_{0} for 0 < x < 1. We have thus proved the claim in all cases for 0 < x ≤ α_{0}. The claim is trivial for x = 0.

Using the claim we can finish the proof writing:

Prob[α_{k+1} ≥ t] ≤ E[f(α_{1})] ≤ E[f_{0}(α_{0})α_{1}/α_{0}] = f_{0}(α_{0})E[α_{1}]/α_{0} =

f_{0}(α_{0})α_{0} = α_{0}^{c+1+log log(1/α_{0})}.

□

We remark that the bound in the lemma is achievable for t = α_{0}^{2^{j}} with an integer 0 ≤ j ≤ k. The optimal process has α_{i} = α_{i−1} or α_{i} = 0 for 1 ≤ i ≤ k − j, while α_{i} = α_{i−1}^{2} for k − j < i ≤ k.

Theorem 7 a) For every ϵ > 0 there is a constant c_{ϵ} > 0 such that the following holds. Let A be a finite set of vectors in a vector space V of an arbitrary dimension over Z_{2}, let t > 0 be an integer. If |A| ≥ c_{ϵ}t2^{t} then for a uniform random linear transformation T : V → Z_{2}^{t}

Prob(T (A) = Z_{2}^{t}) ≥ 1 − ϵ.

b) If A is a subset of the vector space Z_{2}^{u} of density |A|/2^{u} = 1 − α < 1 and 0 ≤ t ≤ u is an integer then for a uniform random onto linear transformation T : Z_{2}^{u} → Z_{2}^{t}

Prob(T (A) ≠ Z_{2}^{t}) ≤ α^{u−t−log t+log log(1/α)}.

Proof: We start with proving part b) of the theorem. In order to pick the onto map T we use the following process (similar to the one in the proof of Theorem 6). Pick s = u − t vectors v_{1}, …, v_{s} uniformly at random from the vectors in Z_{2}^{u} and choose T to be a random onto linear transformation T : Z_{2}^{u} → Z_{2}^{t} with the constraints T (v_{i}) = 0 (i = 1, …, s), i.e. the vectors v_{1}, …, v_{s} are in the kernel of T. Note that the v_{i}’s are not necessarily linearly independent and that they do not necessarily span the kernel. After picking them, an onto transformation satisfying that the v_{i}’s are in the kernel is chosen at random.

Using notations similar to the ones used in the proof of Theorem 6, let A_{0} = A, A_{i} = A_{0} + Span{v_{1}, …, v_{i}} and α_{i} = 1 − |A_{i}|/2^{u} for i = 0, …, s. Clearly α_{i} is nonnegative and monotone decreasing in i with α_{0} = α. The equation E[α_{i+1} | α_{1}, …, α_{i}] = α_{i}^{2} is guaranteed by Lemma 2.1 since A_{i+1} = A_{i} + v_{i+1} and v_{i+1} is independent of α_{j} for j ≤ i. Thus all the conditions of Lemma 2.3 are satisfied and we have

Prob[α_{s} ≥ 2^{−t}] ≤ α^{s−log t+log log(1/α)}.

By the definition of s the right hand side here is equal to the estimate in the theorem. Finally notice that if T (A) ≠ Z_{2}^{t} then for the vector w ∈ Z_{2}^{t} not in T (A) the set T^{−1}(w) of size 2^{u−t} is disjoint from A_{s} and thus α_{s} = 1 − |A_{s}|/2^{u} ≥ |T^{−1}(w)|/2^{u} = 2^{−t}. Thus we have the claimed upper bound for the probability that T (A) ≠ Z_{2}^{t}.

Now we turn to part a) of the theorem and prove it using part b). Part a) is about a random linear transformation, not necessarily onto, but this difference from the claim just proved poses less of a problem, the difficulty is that we do not have an a priori bound on 1 − |A|/|V |. In fact, this ratio can be arbitrarily small. To solve this, we choose the transformation T in two steps, the first step ensuring that the density of the covered set is substantial, then applying part b) for the second step.

Let W = Z_{2}^{u}, with u = ⌈log(2|A|/ϵ)⌉. We factor T through W. First, we pick uniformly at random a linear transformation T_{0} : V → W. Then, we pick a random onto linear map T_{1} : W → Z_{2}^{t}, and set T = T_{0} ∘ T_{1}. This results in a uniformly chosen linear map T : V → Z_{2}^{t}.

Any pair of vectors v ≠ w ∈ A collide with probability Prob[T_{0}(v) = T_{0}(w)] = 1/|W |. Thus the expected number of collisions is \binom{|A|}{2}/|W |. Since |T_{0}(A)| ≤ |A|/2 implies at least |A|/2 such collisions Markov’s inequality gives Prob[|T_{0}(A)| ≤ |A|/2] ≤ 2\binom{|A|}{2}/(|A||W |) < |A|/|W | ≤ ϵ/2. For any fixed T_{0} part b) of the theorem gives

Prob[T (A) ≠ Z_{2}^{t}] ≤ α^{u−t−log t+log log(1/α)},

where α = 1 − |T_{0}(A)|/|W |. In case |T_{0}(A)| > |A|/2 we have α < 1 − |A|/(2|W |) < e^{−ϵ/8}, thus using the monotonicity of the bound above we get

Prob[T (A) ≠ Z_{2}^{t}] ≤ e^{−ϵ(u−t−log t+log(log e^{ϵ/8})/8}.  (1)

Choosing c_{ϵ} = 4(2/ϵ)^{8/ϵ} we have |A| ≥ c_{ϵ}t2^{t} and thus u = ⌈log(2|A|/ϵ)⌉ > t+log t+log(8/ϵ)+(8/ϵ) log(2/ϵ). This implies that the bound in Equation 1 is below ϵ/2, thus we get Prob[T (A) ≠ Z_{2}^{t}] ≤ Prob[|T_{0}(A)| ≤ |A|/2]+ϵ/2 < ϵ as claimed. □

We remark that a more careful analysis gives c_{ϵ} that is a small polynomial of 1/ϵ.

3 The largest bucket

3.1 Lower bound for the largest bucket with a large field

We start by showing why linear hashing over a large finite field is bad with respect to the expected largest bucket size measure. This natural example shows that universality of the class is not enough to assure small buckets. For a finite field F we prove the existence of a bad set S ⊂ F^{2} of size |S| = |F | such that the expected largest bucket in S with respect to a random linear map F^{2} → F is big. We prove the results in Theorem 3 separately for quadratic and non-quadratic fields.

We start with an intuitive description of the constructions. Linear hashing of the plane collapses all straight lines of a random direction. Thus, a bad set in the plane must contain many points on at least one line in many different directions. It is not hard to come up with bad sets that contain many points of many different lines, however the obvious constructions (subplane or grid) yield sets where many of the “popular lines” tend to be parallel and thus they only cover a few directions. This problem can be solved by a projective transformation: the transformed set has many popular lines, but they are no longer parallel.

Theorem 8 Let F be a finite field with |F | being a perfect square. There exists a set S ⊂ F^{2} of size |S| = |F | such that for every linear map h : F^{2} → F, S has a large bucket, i.e. there exists a value y ∈ F with |h^{−1}(y)| ≥ \sqrt{|F |}.

Proof. We have a finite field F_{0} of which F is a quadratic extension. Let |F_{0}| = m and |F | = m^{2} = n. Let a be an arbitrary element in F \ F_{0} and define S = \{(\frac{1}{x+a}, \frac{y}{x+a}) | x, y ∈ F_{0}\}. Note that |S| = m^{2} = |F |. Notice also, that S is the image of the subplane F_{0}^{2} under the projective transformation (x, y) ↦ (\frac{1}{x+a}, \frac{y}{x+a}).

Fix A, B ∈ F and consider the function h : F^{2} → F defined by h(x, y) = Ax+By. We must show that there is some C ∈ F such that |h^{−1}(C)∩S| ≥ m. If B = 0 then h maps all the m elements of S′ = {(1/a, y/a | y ∈ F_{0}} to C = A/a, as needed. Otherwise, we claim that there is a C ∈ F such that both \frac{C}{B} and \frac{aC−A}{B} are in F_{0}. To see this observe that if g_{1} and g_{2} are two distinct members of F_{0}, then ag_{1} and ag_{2} lie in distinct additive cosets of F_{0} in F, since otherwise their difference, a(g_{1} − g_{2}) would have to be in F_{0}, contradicting the fact that a ∉ F_{0}. Thus, as g ranges over all members of F_{0}, ag intersects distinct additive cosets of F_{0} in F, and hence aF_{0} intersects all those cosets. In particular, there is some g ∈ F_{0} so that ag ∈ F_{0}+ \frac{A}{B}, implying that C = gB satisfies the assertion of the claim. For the above C, for every choice of x ∈ F_{0}, y(x) = \frac{C}{B} x + \frac{aC−A}{B} ∈ F_{0}. We have now A\frac{1}{a+x} + B \frac{y(x)}{a+x} = C, showing that h maps all the m elements of S′ = \{(\frac{1}{a+x}, \frac{y(x)}{a+x}) | x ∈ F_{0}\} ⊂ S to C. □

Theorem 9 Let F be a finite field. There exists a set S ⊂ F^{2} of size |S| = |F | such that for more than half of the linear maps h : F^{2} → F, S has a large bucket, i.e. there exists a value y ∈ F with |h^{−1}(y)| ≥ |F |^{1/3}/3 − 1.

Proof. First we construct a set S′ ⊂ F^{2} such that |S′| ≤ |F | = n and there are n distinct lines in the plane F^{2} each containing at least m ≥ n^{1/3}/3 points of S′.

Let us first consider the case when n is a prime, so F consists of the integers modulo n. We let A = \{i | 1 ≤ i < \sqrt{n}\} and consider the square grid S′ = A × A. Clearly |S′| < n. It is well known that each of the n most popular lines contains at least m ≥ n^{1/3}/3 points of S′. This is usually proved for the same grid in the Euclidean plane (see e.g. [PA95], pp. 178–179) but that result implies the same for our grid in F^{2}.

Now let n = p^{k} and let F_{0} be the subfield in F of p elements. Let x ∈ F be a primitive element, then every element of F can be uniquely expressed as a polynomial of x of degree below k with coefficients from F_{0}. Let k_{1} = ⌊\frac{k+1}{3}⌋, k_{2} = k − k_{1} = ⌊\frac{2k+1}{3}⌋ and let A_{1} = \{f(x) | deg(f) < k_{1}\}, A_{2} = {f(x) | deg(f) < k_{2}} where the polynomials f have coefficients from F_{0}. Finally we take S′ = A_{1} × A_{2}. Clearly |S′| = n. For a ∈ A_{1} and b ∈ A_{2} we consider the line L_{a,b} = {(y, ay + b) | y ∈ F } in F^{2}. Notice that there are n such lines and we have ay + b ∈ A_{2} whenever y ∈ A_{1}. Thus, we have n distinct lines each containing m = |A_{1}| = p^{k_{1}} points of S′. We have m ≥ n^{1/3} as claimed unless k ≡ 1 (mod 3). Notice that for k ≡ 2 (mod 3) our m is much higher than n^{1/3}. For the bad case k ≡ 1 (mod 3) we apply the construction below instead.

Finally suppose n = p^{k}, p is a prime and k ≡ 1 (mod 3). To get our set S′ in this case we have to merge the two constructions above. Let F_{0} be the p element subfield of F, then F_{0} consists of the integers modulo p. We set A = \{i | 1 ≤ i < \sqrt{p}\}. Let k_{1} = (k + 2)/3 and k_{2} = (2k + 1)/3 and let x ∈ F be a primitive element, so we can express any element of F uniquely as a polynomial of x of degree less then k with coefficients from F_{0}. We set A_{1} = {f(x) | deg(f) < k_{1}∧f(0) ∈ A}, A_{2} = {f(x) | deg(f) < k_{2}∧f(0) ∈ A} where the polynomials f have coefficients from F_{0}. Finally we set S′ = A_{1} × A_{2}. Clearly |S′| < n. For j, j′ ∈ F_{0} let L_{j,j′} = {(i, ji + j′) | i ∈ F_{0}}. Let a and b be polynomials with coefficients from F_{0} with deg(a) < k_{1} and deg(b) < k_{2}. Consider the line L_{a,b} = {(y, a(x)y + b(x)) | y ∈ F }. Notice that |L_{a,b} ∩ S′| = p^{k_{1}−1}|L_{a(0),b(0)} ∩ (A × A)|. Thus, from knowing that the p most popular lines in F_{0}^{2} contain at least m_{0} ≥ p^{1/3}/3 points from A × A we conclude that there exist n distinct lines each containing at least m = m_{0}p^{k_{1}−1} ≥ n^{1/3}/3 points of S′.

In all cases now we have constructed our set S′ ⊂ F^{2} of size |S′| ≤ n with n distinct popular lines each containing at least m > n^{1/3}/3 points of S′. Let P be the projective plane containing F^{2}. Out of the n^{2} + n + 1 points in P every popular line covers n + 1. The ith popular line (1 ≤ i ≤ n) can only have i − 1 intersections with earlier lines, thus it covers at least n + 2 − i points previously uncovered. Therefore a total of at least \binom{n+2}{2} − 1 points are covered by popular lines. Simple counting gives the existence of a line L in P not among the popular lines, such that more than half of the points on L are covered by popular lines. Let f be a projective transformation taking the ideal line L′ = P \ F^{2} to L. We define S = {x ∈ F^{2} | f(x) ∈ S′}. Clearly |S| ≤ |S′| ≤ n.

One linear hash function h : F^{2} → F is constant zero (and thus all of S is a single bucket), for the rest there is a point x_{h} ∈ L′ such that h collapses the points of F^{2} of each single line going through x_{h}. As we get all points of L′ equal number of times (n − 1 times to be precise) it is enough to prove that whenever f(x_{h}) is covered by a popular line S has a big bucket with respect to h as claimed. So suppose f(x_{h}) is in the popular line L′′. As L′′ contains at least m points of S′ thus f^{−1}(L′′) must be a line through x_{h} containing at least m − 1 points of S (the −1 comes from the possibility of f(x_{h}) ∈ S′).

This ensures a bucket of S with respect to h of size at least m−1 as claimed. □

3.2 Upper bound for the largest bucket with a small field

Let us now recall and prove our main result.

For convenience here we speak about hashing n log n keys to n values. Also, we assume that n is a power of 2. Theorem 5: Let H be the class of linear transformations between two vector spaces over Z_{2}, then

L_{n log n}^{n}(H) = O(log n log log n).

This theorem implies Theorem 4.

We have to bound the probability of the event that many elements in the set S are mapped to a single element in the range. Denote this bad event by E_{1}. The overall idea is to present another (less natural) event E_{2} and show that the probability of E_{2} is small, yet the probability of E_{2} given E_{1} is big. Thus, the probability of E_{1} must be small. We remark here that a somewhat similar line of reasoning was used in the seminal paper of Vapnik and Chervonenkis [VC71].

For the proof we fix the domain to be D = Z_{2}^{m}, the range (the buckets) to be B = Z_{2}^{log n}, and S ⊂ D of size |S| = n log n.

Let us choose arbitrary ℓ ≥ log n and consider the space A = Z_{2}^{ℓ}. We construct the linear transformation h : D → B through the intermediate range A in the following way. We choose uniformly at random a linear transformation h_{1} : D → A and uniformly at random an onto linear transformation h_{2} : A → B. Now we define h =^{def} h_{1} ∘ h_{2}. Note that as mentioned in the proof of part a) of Theorem 7 this yields an h which is uniformly chosen from among all linear transformations from D to B.

Let us fix a threshold t. We define two events. E_{1} is the existence of a bucket of size at least t:

Event E_{1}: There exists an element α ∈ B such that

|h^{−1}(α) ∩ S| > t.

We are going to limit the probability of E_{1} through the seemingly unrelated event E_{2}:

Event E_{2}: There exists an element α ∈ B such that

h_{2}^{−1}(α) ⊆ h_{1}(S).

Consider the distribution space in which h_{1} and h_{2} are uniformly chosen as above. We shall show that

Proposition 3.1 If d = 2^{ℓ}/(n log n) > 1 we have

Prob[E_{2}] ≤ d^{− log d−log log d}.

Proposition 3.2 If t > c_{1/2}(2^{ℓ}/n) log(2^{ℓ}/n) (with c_{1/2} from Theorem 7a)) then

Prob[E_{2}|E_{1}] ≥ \frac{1}{2}.

From Propositions 3.1 and 3.2 we deduce that the probability of E_{1} must be small:

Corollary 3.3 For every c > 1 and every power n of 2 a random linear transformation hashing a subset S of a Z_{2} vector space of size |S| = n log n to Z_{2}^{log n} we have

Prob[maximum bucket size ≥ c log n log log n] < c^{−(1−o(1)) log c}.

Here the o(1) term depends only on c.

Proof: We may suppose that c and n are sufficiently large. We set c′ = c/c_{1/2} with the absolute constant c_{1/2} guaranteed by Theorem 7a) and let ℓ = ⌊log n + log log n + log c′ − 2 log c′/ log log n⌋ to satisfy the condition of Proposition 3.2 with t = c log n log log n. We get Prob[E_{2}|E_{1}] ≥ \frac{1}{2}. Then applying 3.1 we get d > c^{′1−2/ log log n}/2 = c^{1−o(1)}, so in particular d > 1 if c is large enough. Thus, we have Prob[E_{1}] ≤ 2Prob[E_{2}] < 2d^{− log d−log log d} = c^{−(1−o(1)) log c}. □

Let us now prove the propositions above.

Proof of Proposition 3.1: Note first that an alternative way to describe E_{2} is

h_{2}(A \ h_{1}(S)) ≠ B.

We will prove that Proposition 3.1 holds for any specific h_{1}, and thus it also holds for a randomly chosen h_{1}. So fix h_{1} and consider the distribution in which h_{2} is chosen uniformly amongst all full rank linear transformation from A to B.

We use part b) of Theorem 7 for the set A \ h_{1}(S) ⊂ A. Its density is clearly 1 − α for α = |h_{1}(S)|/|A| ≤ |S|/|A| = 1/d. Thus the theorem gives Prob[E_{2}] ≤ α^{ℓ−log n−log log n+log log(1/α)} ≤ d^{− log d−log log d} as claimed. □ Proof of Proposition 3.2: Fix h for which E_{1} holds, and fix any full rank h_{2}. We will show that the probability of event E_{2} is at least 1/2 even when these two are fixed and thus the conditional probability is also at least 1/2.

Now since E_{1} holds there is a subset S′ ⊆ S of cardinality at least t mapped by h to a single element α ∈ Z_{2}^{log n}. Fix this α and define D′ =^{def} h^{−1}(α) and A′ =^{def} h_{2}^{−1}(α). Consider the distribution of h_{1} satisfying h = h_{1} ∘ h_{2}. When we restrict h_{1} to D′, we get that the distribution implied by such h_{1} is a uniform choice of an affine or linear map from D′ into A′ (we show this in Proposition 3.4 below). For event E_{2} to hold it is enough to have A′ ⊆ h_{1}(S). We will show that h_{1}(S′) covers all the points in A′ with probability at least 1/2 and thus we get that event E_{2} happens with probability 1/2. Since h_{2} is onto we have |A′| = 2^{ℓ}/n. On the other hand, D′ ∩ S has cardinality at least t = ⌈c_{1/2}(2^{ℓ}/n) log(2^{ℓ}/n)⌉. By part a) of Theorem 7, the probability that a set of cardinality t mapped by a random linear transformation will cover a range of cardinality 2^{ℓ}/n is at least 1/2. (Note that Theorem 7a) clearly applies to a random affine transformation too.) □

At this point, we have proven Corollary 3.3. This limits the probability of large buckets with linear hashing. It is straightforward to deduce Theorem 5 from that corollary: Proof of Theorem 5: L_{n log n}^{n} is the expectation of the distribution of the largest bucket size. Corollary 3.3 limits the probability of the tail of this distribution, thus yielding the desired bound on the expectation:

E[max S-bucket size] = ∫_{0}^{∞}Prob[max S-bucket > t]dt <

log n log log n(c_{0} + ∫_{c_{0}}^{∞}c^{− log c/2}dc) = O(log n log log n),

if the o(1) term of Corollary 3.3 is below 1/2 for c > c_{0}. □

In order for the paper to be self-contained we include a proof of the simple statement about random linear transformations used above.

Proposition 3.4 Let D, A and B be vector spaces over Z_{2}. Let h : D → B be an arbitrary linear map, and let h_{2} : A → B be an arbitrary onto linear map. Let α be any point in B and denote D′ =^{def} h^{−1}(α) and A′ =^{def} h_{2}^{−1}(α). Then, choosing a uniform linear map h_{1} : D → A such that h = h_{1} ∘ h_{2} and restricting the domain to D′ we get a uniformly chosen linear map from D′ to A′ if α = 0 or uniformly chosen affine map from D′ to A′ otherwise.

Proof: Consider D_{0} =^{def} h^{−1}(0) and A_{0} =^{def} h_{2}^{−1}(0). Let us choose a complement space D_{1} to D_{0} in D, i.e. D_{0} ∩ D_{1} = {0} and D_{0} + D_{1} = D. Let us call x the unique vector in D′ ∩ D_{1}. We have D′ = D_{0} + x. A linear transformation h_{1} : D → A is determined by its two restrictions h′ : D_{0} → A and h′′ : D_{1} → A. Clearly the uniform random choice of h_{1} corresponds to uniform and independent choices for h′ and h′′. The restriction h = h_{1} ∘ h_{2} means that h′(D_{0}) ⊆ A_{0} and h′′ ∘ h_{2} is the restriction of h to D_{1}. Thus, after the restriction the random choices of h′ and h′′ are still independent. Note now that if α = 0 then the restriction of h_{1} in question is exactly h′ : D′ → A′. If α ≠ 0 then use h_{1}(u + x) = h′(u) + h′′(x) for u ∈ D_{0} to note that the restriction in question is again h′, this time translated by the random value h′′(x) ∈ A′. □

4 Remarks and open questions

We have discussed the case of a very small field (size 2) and a very large field (size n). What happens with intermediate sized fields? Some immediate rough generalizations of our bounds are the following: If we hash an adversarily chosen subset of F^{m} of size n = |F |^{k} to F^{k} by a randomly chosen linear map, the expected size of the largest bucket is at most O((log n log log n)^{log |F |}) and at least Ω(|F |^{1/3}). Tighter bounds should be possible.

Another question is which fine-grained property other well known hash families have. Examples of the families we have in mind include: Arithmetic over Z_{p} [CW79, FKS84] (with h_{a,b}(x) = (ax+b mod p) mod n), integer multiplication [DHKP93, AHNR95] (with h_{a}(x) = (ax mod 2^{k}) div 2^{k−l}), Boolean convolution [MNT93] (with h_{a}(x) = a ∘ x projected to some subspace).

An example of a natural non-linear scheme for which the assertion of Theorem 6 fails is the scheme that maps integers between 1 and p, for some large prime p, to integers between 0 and n − 1 for n = ⌈p/m⌉, by mapping x ∈ Z_{p} to the integer part of the fraction (ax + b)( mod p)/m, where a, b are two randomly chosen elements of Z_{p}. For this scheme, there are primes p and choices of an n and a subset S of cardinality Ω(n log n log log log n) of Z_{p}, which is not mapped by the above mapping onto [0, n − 1] under any choice of a and b.

To see this, let p be a prime satisfying p ≡ 3 (mod 4) and consider the set

S = {j^{2} mod p | j ∈ Z_{p} \ {0}},

of all quadratic residues modulo p. Note that for every nonzero element a ∈ Z_{p}, the set aS ( mod p) is either the set of all quadratic residues or the set of all quadratic non-residues modulo p. The main result of Graham and Ringrose [GR90] asserts that for infinitely many primes p, the smallest quadratic nonresidue modulo p is at least Ω(log p log log log p) (this result holds for primes p ≡ 3 ( mod 4) as well, as follows from the remark at the end of [GR90]). Since for such primes p, −1 is a quadratic nonresidue, it follows that for the above S and for any choice of a, b ∈ Z_{p}, the set aS + b (computed in Z_{p}) avoids intervals of length at least Ω(log p log log log p). Choosing m = c log p log log log p for an appropriate (small) constant c, and defining n = ⌈p/m⌉, it follows that |S| = (p − 1)/2 = Ω(n log n log log log n) is not mapped onto [0, n − 1] under any choice of a and b.

A final question is whether there exists a class H of size only 2^{O(log log |U|+log n)} and with L_{n}^{n}(H) = O(log n/ log log n). Note that linear maps over Z_{2}, even combined with collapsing the universe, use O(log log |U| + (log n)^{2}) random bits while the simple scheme using higher degree polynomials uses O(log log |U| + (log n)^{2}/ log log n).

References

[ABI86] N. Alon, L. Babai and A. Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem. J.

Algorithms 7 (1986) 567–583.

[AS92] N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, New York, 1992.

[AHNR95] A. Andersson, T. Hagerup, S. Nilsson, and R. Raman, Sorting in linear time?, in: Proc. 27th ACM Symposium on Theory of Computing, 1995, pp. 427–436.

[CW79] J. L. Carter and M. N. Wegman, Universal classes of hash functions, J. Comput. Syst. Sci. 18 (1979) 143–154.

[CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, 1990.

[DHKP93] M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen, A reliable randomized algorithm for the closest-pair problem, Technical Report 513, Fachbereich Informatik, Universität Dortmund, 1993.

[DM90] M. Dietzfelbinger and F. Meyer auf der Heide, Dynamic hashing in real time, in: J. Buchmann, H. Ganzinger, W. J. Paul (Eds.): Informatik · Festschrift zum 60. Geburtstag von Günter Hotz, Teubner-Texte zur Informatik, Band 1, B. G. Teubner, 1992, pp. 95–119. (A preliminary version appeared under the title “A New Universal Class of Hash Functions and Dynamic Hashing in Real Time” in ICALP’90.)

[DKMHRT94] M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer Auf Der Heide, H. Rohnert, R.E. Tarjan, Dynamic perfect hashing: upper and lower bounds, SIAM J. Comput. 23 (1994) 738–761.

[DGMP92] M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger, Polynomial hash functions are reliable, ICALP’92, Springer LNCS 623, pp. 235–246.

[FKS84] M. L. Fredman, J. Komlós, and E. Szemerédi, Storing a sparse table with O(1) worst case access time, J. Ass. Comput. Mach. 31 (1984) 538–544.

[GBY90] G. Gonnet and R. Baeza-Yates, Handbook of Algorithms and Data Structures, Addison-Wesley, 1991.

[GR90] S. W. Graham and C. J. Ringrose, Lower bounds for least quadratic nonresidues, in: Analytic Number Theory: Proceedings of a Conference in Honor of P.T. Bateman, B. C. Berndt et al. (Eds.), Birkhäuser, Boston, 1990.

[MCW78] G. Markowsky, J. L. Carter, and M. N. Wegman, Analysis of a universal class of hash functions, in: Proc. 7th Conference on Math. Found. of Computer Science (MFCS), 1978, Springer LNCS 64, pp. 345–354.

[MV84] K. Mehlhorn and U. Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories., Acta Informatica 21 (1984) 339–374.

[MNT93] Y. Mansour, N. Nisan, and P. Tiwari, The computational complexity of universal hashing. Theoretical Computer Science 107 (1993) 121–133.

[PA95] J. Pach and P. K. Agarwal, Combinatorial Geometry, Wiley 1995.

[S89] A. Siegel, On universal classes of fast high performance hash functions, their time-space tradeoff, and their application, in: Proc. 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 20–25.

[VC71] V. A. Vapnik and A. Y. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Prob. Applications 16 (1971) 264–280.

Recent BRICS Report Series Publications

RS-97-16 Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and Gábor Tardos. Linear Hashing. June 1997. 22 pp. A preliminary version appeared with the title Is Linear Hashing Good? in The Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pages 465–474.

RS-97-15 Pierre-Louis Curien, Gordon Plotkin, and Glynn Winskel. Bistructures, Bidomains and Linear Logic. June 1997. 41 pp.

RS-97-14 Arne Andersson, Peter Bro Miltersen, Søren Riis, and Mikkel Thorup. Dictionaries on AC^{0} RAMs: Query Time Θ(\sqrt{log n/ log log n}) is Necessary and Sufficient. June 1997. 18 pp. Appears in 37th Annual Symposium on Foundations of Computer Science, FOCS ’96 Proceedings, pages 441–450.

RS-97-13 Jørgen H. Andersen and Kim G. Larsen. Compositional Safety Logics. June 1997. 16 pp.

RS-97-12 Andrej Brodnik, Peter Bro Miltersen, and J. Ian Munro. Trans-Dichotomous Algorithms without Multiplication — some Upper and Lower Bounds. May 1997. 19 pp. Appears in Dehne, Rau-Chaulin, Sack and Tamassio, editors, Algorithms and Data Structures: 5th International Workshop, WADS ’97 Proceedings, LNCS 1272, 1997, pages 426–439.

RS-97-11 Kārlis Čerāns, Jens Chr. Godskesen, and Kim G. Larsen. Timed Modal Specification — Theory and Tools. April 1997. 32 pp.

RS-97-10 Thomas Troels Hildebrandt and Vladimiro Sassone. Transition Systems with Independence and Multi-Arcs. April 1997. 20 pp. Appears in Peled, Pratt and Holzmann, editors, DIMACS Workshop on Partial Order Methods in Verification, POMIV ’96, pages 273–288.

RS-97-9 Jesper G. Henriksen and P. S. Thiagarajan. A Product Version of Dynamic Linear Time Temporal Logic. April 1997. 18 pp. Appears in Mazurkiewicz and Winkowski, editors, Concurrency Theory: 8th International Conference, CONCUR ’97 Proceedings, LNCS 1243, 1997, pages 45–58.

RS-97-8 Jesper G. Henriksen and P. S. Thiagarajan. Dynamic Linear Time Temporal Logic. April 1997. 33 pp.