DIMACS TR: 97-01
Improved Algorithms via Approximations of Probability
Distributions
Authors: Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan
ABSTRACT
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