Randomized Algorithms, LNMB, 2021.
is a graduate course on randomized algorithms.
Randomness is a very powerful idea in theoretical computer science and discrete mathematics. It provides a very useful way to think about problems (usually where one would not expect probability to play any role). This is a huge area, and this course will give a brief glimpse into it.
The course will take place online. The notes for the lectures will be provided here, and the video will be available on a password protected link.
Time: Mondays March 1 – May 10 (except April 5), 11:00-12:45.
There will be 4-5 exercises which will account for the entire grade. Exercises can (and this is encouraged) be done in groups of 2 students. The solutions should be typed in Latex and handed in by the due date.
There is no textbook for the course. But there are two (optional) books.
· Randomized Algorithms by Motwani and Raghavan
· Probability and Computing by Mitzenmacher and Upfal
Another fantastic book on the probabilistic method is
· The probabilistic method by Alon and Spencer.
(Linearity of Expectation)
Lecture 1 (March 1): Introduction
Exercise 1 (due March 22)
Lecture 4 (March
22): Probabilistic method (alterations), Streaming (\ell_0
Links: Data Stream Algorithms (book draft by Chakrabarti) Courses: Thaler Woodruff (more advanced with lecture videos)
Exercise 2 (due April 12)
Lecture 5 (March
29): k-wise independence, Chernoff bounds, Learning from Experts
Links: Terry Tao’s post concentration bounds; Survey on Multiplicative updates and notes on using them to solve LPs and SDPs
Similar courses on the web (with lots of interesting links)
(Anupam Gupta and Shuchi Chawla)