zbMATH — the first resource for mathematics

Small-bias probability spaces: efficient constructions and applications. (English) Zbl 0776.60014
Summary: It is shown 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 \(\varepsilon\)-biased random variables. The number of random bits needed to generate the random variables is \(O(\log n+\log(1/\varepsilon))\). Thus, if \(\varepsilon\) is polynomially small, then the size of the sample space is also polynomial. Random variables that are \(\varepsilon\)-biased can be used to construct “almost” \(k\)-wise independent random variables where \(\varepsilon\) 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 \(\varepsilon\)-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. 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 logarithmic 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.
Reviewer: Reviewer (Berlin)

60C05 Combinatorial probability
60E15 Inequalities; stochastic orderings
94C12 Fault detection; testing in circuits and networks
68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI