MOD_p-tests, Almost Independence and Small Probability Spaces

Abstract

In this paper, we consider approximations of probability distributions over ZZ n p . We present an approach to estimate the quality of approximations of probability distributions towards the construction of small probability spaces. These are used to derandomize algorithms. In contrast to results by Even, Goldreich, Luby, Nisan and Velickovich [EGLNV], our methods are simple, and for reasonably small p, we get smaller sample spaces. Our considerations are motivated by a problem which was mentioned in recent work of Azar, Motwani and Naor [AMN], namely, how to construct in time polynomial in n a good approximation to the joint probability distribution of the random variables X1;X2; : : :;Xn where each Xi has values in f0; 1g and satises Xi = 0 with probability q and Xi = 1 with probability 1