Improved algorithms via approximations of probability distributions (extended abstract)
We present two techniques for approximating probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced in [21]. This construction can be efficiently combined with the method of conditional probabilities to yield improved NC algorithms for many problems such as set cover, set discrepancy, finding large cuts in graphs etc. The second is a construction of small probability spaces approximating general independent distributions, which is of smaller size than the constructions of [13].