Randomness and Pseudo-Randomness in Discrete Mathematics

Szele and others, that deterministic statements can be proved by probabilistic reasoning, led already in the first half of the century to several striking results in Analysis, Number Theory, Combinatorics and Information Theory. It soon became clear that the method, which is now called the probabilis-tic method, is a very powerful tool for proving results in Discrete Mathematics. The early results combined combinatorial arguments with fairly elementary probabilistic techniques, whereas the de-velopment of the method in recent years required the application of more sophisticated tools from probability. The books [10], [54] are two recent texts dealing with the subject. Most probabilistic proofs are existence, non-constructive arguments. The rapid development of theoretical Computer Science, and its tight connection to Combinatorics, stimulated the study of the algorithmic aspects of these proofs. In a typical probabilistic proof, one establishes the existence of a combinatorial structure satisfying certain properties by considering an appropriate probability space of structures, and by showing that a randomly chosen point of this space is, with positive probability, a structure satisfying the required properties. Can we find such a structure efficiently, that is, by a (deterministic or randomized) polynomial time algorithm? In several cases the probabilistic proof provides such a randomized efficient algorithm, and in other cases the task of finding such a