Karl Bringmann: Catalogue data in Spring Semester 2015

NameMr Karl Bringmann
DepartmentComputer Science
RelationshipLecturer

NumberTitleECTSHoursLecturers
263-4100-00LRandomized Algorithms and Probabilistic Methods: Advanced Topics Information 5 credits2V + 1U + 1AJ. Lengler, K. Bringmann, T. S. Luria
AbstractAdvanced introduction to random walks.
ObjectiveStudents will learn some advances techniques to analyze random walks, and they will see some examples of how algorithms make use of random walks. To successfully complete this course students need to be able to apply the acquired techniques and use random walks as a tool for designing algorithms.
ContentThe lecture gives an advanced introduction to random walks. We treat methods to analyze them, and applications in which random walks are used. Some open problems will be discussed as well.
Topics:
- drift analysis
- rapidly mixing random walks
- random sampling and/or approximate counting e.g. of triangulations, latin squares
- expander graphs
- volume estimation of convex bodies
- differential equation method
Prerequisites / NoticeRandomized Algorithms and Probabilistic Methods, or a similar course