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 random variables.

Material available on-line:

• Three 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.
• A new version, February 1997.
• The final version, February 1998.