Note that this course is cross-listed with the ELTE University and is held on their campus. Its schedule is set by ELTE. Time: Fridays, 2-4pm.

Instructor: Dr. László Lovász

Course description:
This course is intended for Master's students. The language of instruction is English.

This semester the main topic is Random walks on graphs and applications.

The study of random walks on finite graphs (closely related to the theory of finite Markov chains) has a long history and a lot of recent applications in algorithm design, simulation, statistical physics and other fields. The computation and estimation of basic quantities is central to these applications. How long does it take (in expectation) to reach a given node? How long before all nodes are visited? After how many steps will we lose all information about the starting position and be anywhere with almost the same probability?

Answers to such questions takes us to linear algebra, the spectrum of graphs, and to algorithms for counting colorings of graphs, for estimating the volume of a convex body, and (time permitting) to better understandin phenomena in statistical physics.