SMALL-BIAS PROBABILITY SPACES - EFFICIENT CONSTRUCTIONS AND APPLICATIONS

It is shown how to efficiently construct a small probability space on n binary random variables such that for every subset, its parity is ei ther zero or one with ''almost'' equal probability. They are called ep silon-biased random variables. The number of random bits needed to gen erate the random variables is O(log n + log 1/epsilon). Thus, if epsil on is polynomially small, then the size of the sample space is also po lynomial. Random variables that are epsilon-biased can be used to cons truct ''almost'' k-wise independent random variables where epsilon is a function of k. These probability spaces have various applications: 1 . Derandomization of algorithms: Many randomized algorithms that requi re only k-wise independence of their random bits (where k is bounded b y O(log n)), can be derandomized by using epsilon-biased random variab les. 2. Reducing the number of random bits required by certain randomi zed algorithms, e.g., verification of matrix multiplication. 3. Exhaus tive testing of combinatorial circuits. The smallest known family for such testing is provided. 4. Communication complexity: Two parties can verify equality of strings with high probability exchanging only a lo garithmic number of bits. 5. Hash functions: A polynomial sized family of hash functions such that with high probability the sum of a random function over two different sets is not equal can be constructed.