Date: Mon, 25 Nov 1996 22:03:31 GMT Server: NCSA/1.4.1 Content-type: text/html Last-modified: Wed, 09 Aug 1995 00:13:41 GMT Content-length: 4947 Alan Siegel

Alan Siegel

Associate Professor, Computer Science Dept

Alan Siegel@cs.nyu.edu


Department of Computer Science
Courant Institute of Mathematical Sciences
New York University


Mail Address

Courant Inst. of Math. Sciences, rm 413
251 Mercer St.
New York, NY 10012, U.S.A.

Phones

212.998.3122 (voice) 212.995.4121 (fax)

Email

Alan Siegel@cs.nyu.edu

Topics

tr684
A. Siegel, "On Universal Classes of Extremely Random Constant Time Hash Functions and their Time-space Tradeoff", Apr. 1995

Abstract: A family of functions F that map [0,n]->[0,n], is said to be h-wise independent if any h points in [0,n] have an image, for randomly selected f in F, that is uniformly distributed. This paper gives both probabilistic and explicit randomized constructions of (n**epsilon)-wise independent functions, for epsilon<1, that can be evaluated in constant time for the standard random access model of computation. Simple extensions give comparable behavior for larger domains. As a consequence, many probabilistic algorithms can for the first time be shown to achieve their expected asymptotic performance for a feasible model of computation.

This paper also establishes a tight tradeoff in the number of random seeds that must be precomputed for a random function that runs in time T and is h-wise independent.

tr685
A. Siegel, "Toward a Usable Theory of Chernoff Bounds for Heterogeneous and Partially Dependent Random Variables", Apr. 1995

Abstract: Let X be a sum of real valued random variables and have a bounded mean E[X]. The generic Chernoff-Hoeffding estimate for large deviations of X is: P{X-E[X]>=a}<=min_{y>=0}exp(-y(a+E[X]))E[exp(y X)], which applies with a>=0 to random variables with very small tails. At issue is how to use this method to attain sharp and useful estimates. We present a number of Chernoff-Hoeffding bounds for sums of random variables that may have a variety of dependent relationships and that may be heterogeneously distributed.

tr686
J. Schmidt, A. Siegel, "Double Hashing is Computable and Randomizable with Universal Hash Functions", Apr. 1995

Abstract: Universal hash functions that exhibit (c log n)-wise independence are shown to give a performance in double hashing and virtually any reasonable generalization of double hashing that has an expected probe count of 1/(1-alpha) + epsilon for the insertion of the (alpha n)-th item into a table of size n, for any fixed alpha < 1 and epsilon > 0. This performance is within epsilon of optimal. These results are derived from a novel formulation that overestimates the expected probe count by underestimating the presence of partial items already inserted into the hash table, and from a sharp analysis of the underlying stochastic structures formed by colliding items.

tr687
A. Siegel, J. Schmidt, "Closed Hashing is Computable and Optimally Randomizable with Universal Hash Functions", Apr. 1995

Abstract: Universal hash functions that exhibit (c log n)-wise independence are shown to give a performance in double hashing, uniform hashing and virtually anyreasonable generalization of double hashing that has an expected probe count of 1/(1-alpha)+O(1/n) for the insertion of the (alpha n)-th item into a table of size n, for any fixed alpha < 1. This performance is optimal. These results are derived from a novel formulation that overestimates the expected probe count by underestimating the presence of local items already inserted into the hash table, and from a very sharp analysis of the underlying stochasticstructures formed by colliding items.

Analogous bounds are attained for the expected r-th moment of the probe count, for any fixed r, and linear probing is also shown to achieve a performance with universal hash functions that is equivalent to the fully random case.

  • NYU Tech Reportshypertext