|
Abstract : |
We show how to efficiently construct a small probability space on n binary random variables such that for every subset, its parity is either zero or one with "almost " equal probability. They are called ffl-biased random variables. The number of random bits needed to generate the random variables is O(log n + log 1 ffl). Thus, if ffl is polynomially small, then the size of the sample space is also polynomial. Random variables that are ffl-biased can be used to construct "almost " k-wise independent random variables where ffl is a function of k. These probability spaces have various applications: 1. Derandomization of algorithms: many randomized algorithms that require only k-wise independence of their random bits (where k is bounded by O(log n)), can be derandomized by using ffl-biased random variables. 2. Reducing the number of random bits required by certain randomized algorithms, e.g., verification of matrix multiplication. 3. Exhaustive testing of combinatorial circuits. We provide the smallest known family for such testing. 4. Communication complexity: two parties can verify equality of strings with high probability exchanging only a logarithmic number of bits. 5. Hash functions: we can construct 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., |
