Dates: Sept. -Dec. 2003.
A tentative schedule is given below.

Course Description "Why do randomized algorithms work?" A short answer is: randomized algorithms work well because of the concentration of measure phenomenon : even though the possible outcomes are potentially large in number, the actual outcome is usually concentrated in a very narrow range. The course is an introduction to tools that help us establish concentration of measure. We will cover the some central techniques that provide tools for the so-called "high probability" analysis of randomized algorithms i.e they allow us to make precise statements about the reliability with which we can assert that the outcomes of an algorithm will be in a narrowly specified range. In particular, we will cover the following topics:

• Chernoff-Hoeffding bounds.
• Martingale inequalities and the "method of bounded differences".
• Isoperimetric inequalities via information theory.
• Talagrand's "convex distance" inequality.
• Log-Sobolev inequalities.

Examination: To pass the course, students need to:

• Turn in 5 problem sets (to appear here later!).
  • Problem Set 1 (Due Sept. 17.)
  • Problem Set 2 (Due Sept. 30.)
  • Problem Set 3 (Due Nov. 3)
• Choose a topic for study from a selected list (to appear here later) or elsewhere related to the material of the course and give a short presentation.

• CH Bounds
  • S. Jansson, "Large Deviations for Sums of Partially Dependent Random Variables", unpublished manuscript available from Jansson's web page. [Gives a nice extension of thr CH bound which applies when the variables have limited dependence as quantified by a dependency graph.]
• Martingale inequalities
  • J-H Kim and V. Vu, "Divide and Conquer Martingales", unpublished manuscript aavailable from Kim's web page. [Gives a refinement of the martingale inequalities.]
• Large Deviations in Markov Chains
  • N. Kahale, "Large Deviations for Markov Chains",
  • D. Gillman, "A Chernoff Bound for Random Walks on Expander Graphs", SIAM J. Computing , 27:4, pp. 1203 -- 1220, 1998.
• Brunn-Minkowski Inequality
  • R. J. Gardner, "The Brunn-Minkowski Inequality", Bull. of the AMS , 39:3, pp. 355-405, 2002. [Fascinating survey of the landscape of fundamental inequalites and their relationships. Hints at relations to isoperimetric inequalities, transportation inequalities, log-Sobolev inequalities, and more!]
  • S.G. Bobkov and M. Ledoux, "From Brunn-Minkowski to Brascamp-Lieb and to Logarithmic Sobolev Inequalities", GAFA Geom. Funct. Analysis 10, pp. 1028-1052, 2000.

• A draft of a forthcoming monograph on the topic to be published in the Springer series "Algorithms and Combinatorics". Chapters will be placed here as the lectures progress.
• C. McDiarmid, "Concentration" in M. Habib et al (ed) Probabilistic Methods in Algorithmic Discrete Mathematics Springer-Verlag 1998. [An authoritative survey especially on CH bounds and Martingale methods. It was McDiarmid who popularised the "method of bounded difefrences".]
• J. M. Steele, Probability Theory and Combinatorial Optimization CBMS-NSF Regional Conference Series in Applied Mathematics, 69. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. Buy it here! We will cover material mainly from Chapters 1 and 6.
• M. Ledoux, The Concentration of Measure Phenomenon [For the serious mathematician!]

• Many of the results in Olle's course were statements true in the limit. We will focus on statements that hold in the finite case. For example, we want bounds on the probbaility of large deviations of a sum of n random variables (not the limit as n goes to infty). (This is clearly motivated by algorithmic considerations.)
• We will be interested only in upper bounds on probabilities of large deviations (so we won't care about exact matching upper and lower bounds that hold in the limit).
• We will be interested in large deviations of arbitrary functions of random variables, not just their sum. Once again, this is motivated by algorithmic considerations where the result of an algorithm is often some complicated function of the random variables not simply their sum.
• We will be interested in cases where the random variables involved are not independent. Most of the results in Olle's course were derived in the iid case, but in algorithmic applications, this is often not the case, especially not independence.