This project will study randomized algorithms to solve information storage and retrieval problems. Specifically, the project will focus on randomized hashing schemes, which enable the quick retrieval of any item stored in a table. In the hashing shcemes considered, a hashing function is randomly chosen from a small universal class of hashing functions, and good average performance is guaranteed for arbitrary data. Such classes of universal functions provide important progress in closing the gap between idealized models and the situations that one is faced with in practice. Various closed hashing schemes, in which all items are placed in a table and no pointers are available, will be investigated. The techniques developed for analyzing the interactions which occur in a closed hash table are likely to be extendible to the analysis of other randomized constructions. A key problem that arises in a randomized algorithm is that its performance depends on the generation of random variables. Since pseudo-random variables are used in practice, it is very important to analyze how independent the generated variables need to be in order to ensure the predicted performance. Such analysis provides a measure of how robust the randomized algorithm is. Several randomized schemes will be investigated to determine whether, in exchange for some degradation in performance and some changes in the algorithm, functions with very limited independence may be used as well.
