返回Google圖書搜尋

Tiny Families of Functions with Random Properties: a Quality-size Trade-off for Hashing

Mekhon Ṿaitsman le-madaʻ. Department of Applied Mathematics and Computer ScienceOded Goldreich

出版	Weizmann Institute of Science, Department of Applied Mathematics and Computer Science, 1994
URL	http://books.google.com.hk/books?id=tWLvGwAACAAJ&hl=&source=gbs_api

註釋Abstract: "We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family), and the quality (or error parameter) of the pseudo-random property it achieves. Unlike previous constructions, most notably universal hashing, the size of our families is essentially independent of the size of the domain on which the functions operate. The first construction is for the mixing property -- mapping a proportional part of any subset of the domain to any other subset. The other two are for the extraction property -- mapping any subset of the domain almost uniformly into a range smaller than it. The second and third constructions handle (respectively) the extreme situations when the range is very large or very small. We provide lower bounds showing our constructions are nearly optimal, and mention some applications of the new constructions."