Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Small sample spaces:
TR94-002 | 12th December 1994
Oded Goldreich, Avi Wigderson

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

Revisions: 2

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, ... more >>>

TR02-048 | 31st July 2002
Noga Alon, Oded Goldreich, Yishay Mansour

Almost $k$-wise independence versus $k$-wise independence

We say that a distribution over $\{0,1\}^n$
is almost $k$-wise independent
if its restriction to every $k$ coordinates results in a
distribution that is close to the uniform distribution.
A natural question regarding almost $k$-wise independent
distributions is how close they are to some $k$-wise
independent distribution. We show ... more >>>

ISSN 1433-8092 | Imprint