Course Identification

Students are expected to be familiar with algorithms, complexity theory, probability theory, and linear algebra, at an undergraduate level.

Algorithms that are randomized, i.e. use coin tosses during their execution, are central in many computational scenarios, and have become a key tool in Theoretical Computer Science and in application areas. The course will cover the development and use of such probabilistic techniques, including some of the following topics: Concentration results; Simulating randomness, in particular limited independence; Load balancing; Routing algorithms; Randomized rounding; Sampling and sublinear algorithms; Algorithms in the data stream model; Communication protocols and the sketching model.

Upon successful completion of this course students should be able to:
[1] Analyze probabilistic events and randomized processes.
[2] Design algorithms that use randomness, and analyze their performance.
[3] Make use of basic tools such as first and second moment, concentration bounds, balls and bins, birthday paradox.
[4] Describe and apply algorithmic paradigms that rely on randomness like hashing, sampling, sketching, and streaming.