--logo--

Mathematics in Science and Society

Department of Mathematics, University of Illinois at Urbana-Champaign

presenting a talk by

Noga Alon
Tel Aviv University
Institute for Advanced Study, Princeton

on

Randomness and Pseudo-Randomness in Discrete Mathematics

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.

Tuesday, September 10, 1996, 4:00, Room 241, Altgeld Hall

Refreshments at 3:15 pm in Room 321, Altgeld Hall.

Sign up for dinner with the speaker at Timpone's at 6:30.