Randomness and Computation

Spring 2013

One of the most remarkable developments in Computer Science over the past 30 years has been the realization that the ability of computers to toss coins can lead to algorithms that are more efficient, conceptually simpler and more elegant that their best known deterministic counterparts. Randomization has by now become a ubiquitous tool in computation.

This course will survey several of the most widely used techniques in this context, illustrating them with examples taken from algorithms, random structures and combinatorics. Our goal is to provide a solid background in the key ideas used in the design and analysis of randomized algorithms and probabilistic processes.

Course Information

Instructor: Ilias Diakonikolas
Lectures: Tuesdays 14:00-15:50, in Forrest Hill, Room B1.
Course catalogue entry
Textbook: The required textbook for the course is Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal.
Assessment: A written examination contributes 70% of the final grade. The remaining 30% will be based on two (pencil and paper) homework exercises.

Course Outline

Here is a rough outline of the course material:

Introduction: Las Vegas and Monte Carlo algorithms
- Elementary Examples: checking identities, fingerprinting

Moments, Deviations and Tail Inequalities
- Balls and Bins, Coupon Collecting, stable marriage, routing

Randomization in Sequential Computation
- Data Structures, Graph Algorithms

Randomization in Parallel and Distributed Computation
- Algebraic techniques, matching, sorting, independent sets

Randomization in Online Computation
- Online model, adversary models, paging, k-server

The Probabilistic Method
- Threshold phenomena in random graphs, Lovasz Local Lemma

Random Walks and Markov Chains
- Hitting and cover times, Markov chain Monte Carlo

Lectures

Lecture 1 (January 15) Introduction. Elementary examples: identity testing, verifying matrix multiplication, randomized min-cut. (Chapter 1 of [MU]). Slides.
Lecture 2 (January 22) Review of Discrete Probability (random variables, independence, expectation, variance, moments). Markov's inequality, Jensen's inequality, Chebyshev's inequality. Application: Coupon collector's problem. (Sections 2.1, 2.2, 2.4 and 3.1-3.3 of [MU]).
Lecture 3 (January 29) Analysis of Randomized Quicksort and Randomized Median. (Sections 2.5 and 3.4 of [MU]).
Lecture 4 (February 5) Chernoff Bounds. (Sections 4.1-4.4 of [MU]).
Lecture 5 (February 12) Balls and Bins. (Sections 5.1-5.4 of [MU]).
Lecture 6 (February 26) The Probabilistic Method. (Sections 6.1-6.4 of [MU]).
Lecture 7 (March 5) Markov Chains. (Sections 7.1-7.3 of [MU]).
Lecture 8 (March 12) The Monte Carlo Method. (Sections 10.1-10.3 of [MU]).
Lecture 9 (March 19) The Second Moment Method, Lovasz Local Lemma. (Sections 6.5, 6.7 of [MU]).
Lecture 10 (March 26) Lovasz Local Lemma continued, Random Walks on Graphs. (Sections 6.7, 7.4 of [MU]).
Lecture 11 (April 2) Course summary. Other topics (Introduction to Computational Learning).

Homeworks

Problem Set 1 Due on March 12 before class. ps1.pdf.
Problem Set 2 Due on April 12, 4pm. ps2.pdf.