Approximations of General Independent Distributions
Guy Even, Oded, Michael Luby, Noam Nisan, Boban Velickovic
We describe efficient constructions of small probability spaces
that approximate the joint distribution for general random variables.
Previous work on efficient constructions concentrate on approximations
of the joint distribution for the special case of uniform boolean-valued
Material available on-line:
old texts, dating November 1991. Specifically,
- The STOC92 proceeding version.
- A personal version which has appeared nowhere
and contains only part of the material alas in different presentation.
- Additional material from Guy's master thesis
which is referred to in the above versions:
a construction of small bias sample spaces over GF(p),
for p greater than 2.
new version, February 1997.
final version, February 1998.
list of papers,
list of complexity papers.