The first result is a very general bound of Chernoff on the probability that a sum of n independent identically distributed random variables will exceed the expected value. The talk will touch upon applications to randomized algorithms for routing and sorting problems.
The second result, referred to as the Lovasz Local Lemma, gives a simple condition for there to be a nonzero probability that none of a set of interrelated events occurs. The condition is based only upon a bound on the probability of each individual event occurring and a bound on the number of other events upon which each event depends. The result is valuable to prove the existence of certain problem solutions, e.g., a short schedule for routing messages in a network. In addition, a recent version of the Lemma by Beck can be applied to the development of efficient algorithms for actually finding solutions to some problems. Time permitting, the talk will also sketch Bach's application of a theorem of Weil in algebraic geometry to the design of probabilistic algorithms. Most analyses of randomized algorithms assume that there is a source from which one may obtain many independent random values. Bach analyzes the approach more typically used in practice of attempting to start with one random seed and then using a pseudorandom number generator to get the other "random" values. He shows that certain randomized algorithms have very low failure probability even under the more reasonable assumption of just the initial seed value being random. For a particular example, we will look at an algorithm for computing square roots modulo a prime.
Intended audience: A general mathematical audience, including participants of the Ross program.
The talk is suitable for all ages. Those with some mathematical background should find plenty to keep themselves occupied, while those less experienced can enjoy the juggling and the exposition of this ancient skill.