@article {17603, title = {Improved Algorithms via Approximations of Probability Distributions}, journal = {Journal of Computer and System Sciences}, volume = {61}, year = {2000}, month = {2000/08//}, pages = {81 - 107}, abstract = {We present two techniques for constructing sample spaces that approximate 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 parallel algorithms for problems such as set discrepancy, finding large cuts in graphs, and finding large acyclic subgraphs. The second is a construction of small probability spaces approximating general independent distributions which are of smaller size than the constructions of Even, Goldreich, Luby, Nisan, and Veli{\v c}kovi{\'c}.}, keywords = {derandomization, discrepancy, explicit constructions, graph coloring, Parallel algorithms, small sample spaces}, isbn = {0022-0000}, doi = {10.1006/jcss.1999.1695}, url = {http://www.sciencedirect.com/science/article/pii/S0022000099916951}, author = {Chari,Suresh and Rohatgi,Pankaj and Srinivasan, Aravind} }