Randomness and Pseudo-Randomness in Discrete Mathematics

                        Noga Alon

                  Tel Aviv University 
                   and IAS, Princeton

The discovery, demonstrated in the early work of Erdos, Shannon 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 probabilistic method, is a very powerful tool for proving
results in Discrete Mathematics.

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.

The application of probabilistic techniques for proving deterministic
theorems, and the application of deterministic theorems for
derandomizing probabilistic existence proofs, form an interesting
combination of mathematical ideas from various areas, whose intensive
study  in recent years led to the development of fascinating
techniques. I will survey some of these developments and describe
several related open problems.

----------------------------------

Noga Alon is a Baumritter Professor of Mathematics in Tel Aviv
University, Israel. He received his Ph. D. in  Mathematics in the
Hebrew University of Jerusalem in 1983 and had visiting positions in
various research institutes including MIT, The Institute for Advanced
Study in Princeton, IBM Almaden Research Center, Bell Laboratories and
Bellcore. He serves on the editorial boards of eleven technical
journals and has given invited lectures in many conferences, including
a plenary address in the 1996 European Congress of Mathematics and
an invited lecture in 
the 1990 International Congress of Mathematicians.  He published more
than two hundred research papers, mostly in Combinatorics and in
Theoretical Computer Science, and one book coauthored by J. Spencer;
"The Probabilistic Method" (Wiley, 1992).  He received the
Erdos prize in 1989 and the Feher prize in 1991.