Topics in Probabilistic Methods for Discrete Mathematics

Instructor: Hemanshu Kaul

Office: 238, M.E.B. (and 178, Altgeld Hall)
Phone: 217-244 0292 (office)
E-mail: hkaul [at] math [dot] uiuc [dot] edu

Time: 4pm, Monday and Wednesday (occasionally, 4pm Friday)
Place: 241, Altgeld Hall

Course Information: A detailed description of the lecture topics is available in the course proposal .
In brief, the lectures will discuss three areas and their applications that are not well covered in other graduate courses: Concentration of Measure (large deviation inequalities), Applications of Entropy, and Rapidly Mixing Markov Chains (Markov Chain Monte Carlo). The lectures will present elementary proofs of basic results in these areas. The focus will be on developing the themes underlying the various methods and illustrating the final results through applications in graph theory, combinatorial optimization and theoretical computer science. Some past exposure to probability or probabilistic methods will be helpful.

Class Announcements:

Class Log: