Hashing with linear probing dates back to the 1950s and is among the most widely studied algorithms. In recent years, it has become one of the most important hash table organizations because it uses the cache of modern computers very well. Unfortunately, previous analyses relied either on complicated and space-consuming hash functions, or on the unrealistic assumption of free access to a hash function with random and independent function values. Carter and Wegman, in their seminal paper on universal hashing, have already raised the question of extending their analysis to linear probing. However, we show in this paper that linear probing using a pairwise independent family may have expected logarithmic cost per operation. On the positive side, we show that 5-wise independence is enough to ensure constant expected time per operation. This resolves the question of finding a space- and time-efficient hash function that provably ensures good performance for linear probing.

We present a new technique of universe reduction. Primary applications are the dictionary problem and the predecessor problem. We give several new results on static dictionaries in different computational models: the word RAM, the practical RAM, and the cache-oblivious model. All algorithms and data structures are deterministic and use linear space. Representative results are: a dictionary with a lookup time ofO(log logn) and construction time ofO(n) on sorted input on a word RAM, and a static predecessor structure for variable- and unbounded length binary strings that in the cache-oblivious model has a query performance ofO(|s|/B+ log |s|) I/Os, for query arguments.

We consider the *approximate sparse recovery problem*, where the goal is to (approximately) recover a high-dimensional vector x from Rn from its lower-dimensional *sketch* Ax from Rm.Specifically, we focus on the sparse recovery problem in the L1 norm: for a parameter k, given the sketch Ax, compute an approximation x' of x such that the L1 approximation error | |x-x'| | is close to minimum of | |x-x*| | over all vectors x* with at most k terms. The sparse recovery problem has been subject to extensive research over the last few years.Many solutions to this problem have been discovered, achieving different trade-offs between various attributes, such as the sketch length, encoding and recovery times.In this paper we provide a sparse recovery scheme which achieves close to optimal performance on virtually all attributes. In particular, this is the first recovery scheme that guarantees k log(n/k) sketch length, and near-linear n log (n/k) recovery time *simultaneously*. It also features low encoding and update times, and is noise-resilient.

We present a new analysis of the well-known family of multiplicative hash functions, and improved deterministic algorithms for selecting “good” hash functions. The main motivation is realization of deterministic dictionaries with fast lookups and reasonably fast updates. The model of computation is the Word RAM, and it is assumed that the machine word-size matches the size of keys in bits. Many of the modern solutions to the dictionary problem are weakly nonuniform, that is, they require a number of constants to be computed at “compile time” for the stated time bounds to hold. The currently fastest deterministic dictionary uses constants not known to be computable in polynomial time. In contrast, our dictionaries do not require any special constants or instructions, and running times are independent of word (and key) length. Our family of dynamic dictionaries achieves a performance of the following type: lookups in time O ( t ) and updates in amortized time O ( n 1/ t ), for an appropriate parameter function t . Update procedures require division, whereas searching uses multiplication only.

Hashing with linear probing dates back to the 1950s, and is among the most studied algorithms. In recent years it has become one of the most important hash table organizations since it uses the cache of modern computers very well. Unfortunately, previous analyses rely either on complicated and space consuming hash functions, or onthe unrealistic assumption of free access to a truly random hash function. Already Carter and Wegman, in their seminal paper on universal hashing, raised the question of extending their analysis to linear probing.

We consider deterministic dictionaries in the parallel disk model, motivated by applications such as file systems. Our main results show that if the number of disks is moderately large (at least logarithmic in the size of the universe from which keys come), performance similar to the expected performance of randomized dictionaries can be achieved. Thus, we may avoid randomization by extending parallelism. We give several algorithms with different performance tradeoffs. One of our main tools is a deterministic load balancing scheme based on expander graphs, that may be of independent interest. Our algorithms assume access to certain expander graphs "for free". While current explicit constructions of expander graphs have suboptimal parameters, we show how to get near-optimal expanders for the case where the amount of data is polynomially related to the size of internal memory.