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)