אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב
פרופ' נגה אלון (אונ' ת"א, זוכה פרס ישראל 2008)
יום רביעי, 23.07.2008, 16:30
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.