Improved algorithms via approximations of probability distributions

We present two techniques for constructing sample spaces that approximate p robability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to efficiently combine this construction with the method of conditional probab ilities to yield improved parallel algorithms for problems such as set disc repancy, finding large cuts in graphs, and finding large acyclic subgraphs. The second is a construction of small probability spaces approximating gen eral independent distributions which are of smaller size than the construct ions of Even, Goldreich, Luby, Nisan, and Velickovic. (C) 2000 Academic Pre ss.