Randomized Algorithms, LNMB, 2021.

Nikhil Bansal and Rene Sitters

This 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.

Evaluation:

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.

Lecture Notes:

Handout (Linearity of Expectation)

Lecture 1 (March 1): Introduction

Lecture 2 (March 8): Basic Algorithms Links: Randomized min-cut,

Exercise 1 (due March 22)

Lecture 3 (March 15): 2-SAT, Polynomial identity test, probabilistic method (basics) Links: Random Walk 2-SAT Probabilistic method

Lecture 4 (March 22): Probabilistic method (alterations), Streaming (\ell_0 and \ell_2)
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)

UC Berkeley (Luca Trevisan)
UBC (Nick Harvey)
CMU (Anupam Gupta and Shuchi Chawla)
UW (James Lee)