MATH 261B
Topics in Probabilistic Combinatorics and Algorithms
Winter, 2012
Lecturer: Professor Fan Chung Graham
Time: T Th 12:30-1:50pm
Place: 7421 APM
Office Hours: T 2-3pm APM7101
This course will cover combinatorial probabilistic methods, with special
emphasis
on applications of concentration inequalities in a number of areas, including
the analysis of randomized algorithms, pagerank algorithms, local
algorithms based on random walks, and the study of complex networks.
This course is NOT necessarily a continuation of 261A. The prerequisites
are linear algebra, graph theory and probability.
Suggested (but not required) books:
-
Concentration of Measure for the Analysis of Randomized Algorithms,
by D. P. Dubhashi and A. Panconesi
-
Graph Colouring and the Probabilistic Method
by M. Molloy and B. Reed.
-
Reversible Markov Chains and Random Walks on Graphs,
(Monograph in preparation)
by D. Aldous and J. Fill.
http://www.stat.berkeley.edu/users/aldous/RWG/book.html
-
Spectral Graph Theory
by F. Chung, CBMS Lecture Notes, AMS Publications, 1992.
The first four chapters are available on-line.
-
Complex Graphs and Networks
by F. Chung and L. Lu, CBMS Lecture Notes, AMS Publications, 2006.
The first three chapters are available on-line.
The second chapter is entirely on concentration inequalities.
-
Randomized Algorithm
by R. Motwani and
P. Raghavan.
Announcements
|Reading
|Notes and Presentations
|Final Exam
Back