Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR94-002 | 11th December 1996 00:00

Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing

RSS-Feed




Revision #2
Authors: Oded Goldreich, Avi Wigderson
Accepted on: 11th December 1996 00:00
Downloads: 3299
Keywords: 


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 {\em mixing} property --
mapping a proportional part of any subset of the domain
to any other subset. The other
two are for the {\em 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.}


Revision #1 to TR94-002 | 22nd January 1996 00:00

Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing





Revision #1
Authors: Oded Goldreich, Avi Wigderson
Accepted on: 22nd January 1996 00:00
Downloads: 3411
Keywords: 


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 {\em mixing} property --
mapping a proportional part of any subset of the domain
to any other subset. The other
two are for the {\em 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.}


Paper:

TR94-002 | 12th December 1994 00:00

Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing





TR94-002
Authors: Oded Goldreich, Avi Wigderson
Publication: 12th December 1994 00:00
Downloads: 3908
Keywords: 


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 {\em mixing} property --
mapping a proportional part of any subset of the domain
to any other subset. The other
two are for the {\em 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.



ISSN 1433-8092 | Imprint