Next: Knowledge Complexity and Computational
Up: The Technion Period (1986-94)
Previous: Lower Bounds for Sampling
This work presents families of hashing functions
that posses two random properties of universal hashing functions;
specifically, the extraction and mixing properties.
The size of these families is polynomially related the the
parameter that determines the quality of these properties.
Comments:
Authored by O. Goldreich and A. Wigderson. Appeared in
- Proc. of the 26th STOC,
pp. 574-583, 1994.
- Journal of Random structures and Algorithms,
Volume 11, Number 4, December 1997, pages 315-343.
Oded Goldreich
2003-07-30