DIMACS TR: 97-01

Improved Algorithms via Approximations of Probability Distributions

Authors: Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan


We present two techniques for approximating probability 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 probabilities to yield improved NC algorithms for many problems such as set discrepancy, finding large cuts in graphs, finding large acyclic subgraphs etc. The second is a construction of small probability spaces approximating general independent distributions, which is of smaller size than the constructions of Even, Goldreich, Luby, Nisan and Velickovic. Such approximations are useful, e.g., for the derandomization of certain randomized algorithms.

In addition to other support, Aravind Srinivasan's research was supported in part by NSF grant NSF-STC91-19999 to DIMACS and by support to DIMACS from the New Jersey Commission on Science and Technology.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-01.ps.gz

DIMACS Home Page