The Taub Faculty of Computer Science Events and Talks

Abstract: The discovery that deterministic statements can be proved by probabilistic reasoning, led already more than fifty years ago to several striking results in various mathematical disciplines. 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.

After some light examples that illustrate the fact that probabilistic arguments may be counter-intuitive, I will sketch some recent applications of probabilistic ideas in the design of efficient algorithms and in the proofs of combinatorial statements.

The main theme is that a probabilistic point of view may be very helpful even when we are interested only in purely deterministic algorithms,or in purely deterministic mathematical statements.