1990 · 198 citations · 31 references
Natural SciencesComputer ScienceMathematicsMachine LearningProbability TheoryStatisticsMarkov Chain Monte CarloRandomized Computation
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 e-biased random variables. The number of random bits needed to generate the random variables is O(logn log ~). Thus, if e is polynomially small, then the size of the sample space is also polynomial. e-biased random variables can be used to construct "almost" k-wise independent random variables where e is a function of k. Applications are shown to derandomization of algorithms, reducing the number of random bits required by certain randomized algorithms, exhaustive testing of combinatorial circuits, communication complexity and construction of hash functions.
31
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Michael Luby · SIAM Journal on Computing · 1986 · 1.1K citations
Noam Nisan, Avi Wigderson · Journal of Computer and System Sciences · 1994 · 821 citations