Random Structures and Algorithms · 1991 · 193 citations · 14 references
ComputingComputer ScienceMathematicsAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisParallel Algorithm DesignDeterministic Parallel AlgorithmsDeterministic Parallel SearchLovász Local LemmaMathematical Existence ProofsParallel Search Algorithms
Abstract The Lovasz Local Lemma is a tool that enables one to show that certain events hold with positive, though very small probability. It often yields existence proofs of results without supplying any efficient way of solving the corresponding algorithmic problems. J. Beck recently has found a method for converting some of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates. His method does not seem to be parallelizable. Here we modify his technique and achieve an algorithmic version that can be parallelized, thus obtaining deterministic NC l algorithms for several interesting algorithmic problems.
14
The Art of Computer Programming
G.E. Whitesides · Nuclear Science and Engineering · 1970 · 6.1K citations
Noga Alon, Colin McDiarmid, Bruce Reed · Random Structures and Algorithms · 1991 · 232 citations
Simple construction of almost k-wise independent random variables
Noga Alon, Oded Goldreich, Johan Håstad et al. · 2002 · 159 citations