CS574: Randomized Algorithms

Fall 2015




Randomness has proven itself to be a useful resource for developing provably efficient algorithms and protocols. As a result, the study of randomized algorithms has become a major research topic in recent years. This course will explore techniques for effectively using randomization and for analyzing randomized algorithms, as well as examples from a variety of settings and problem areas. A tentative syllabus can be found here.


Mathematical maturity; exposure to advanced undergraduate material in Algorithms, and in Discrete Probability and Combinatorics. More specifically, CS 374, and MATH 461 or STAT 400 or equivalent are required.

If you have not taken those classes but believe that your background is close to being sufficient, please make sure you have filled up any potential gaps by the end of the second week of classes (September 8). You can refer to the standard algorithms and probability textbooks for the classes above as supplementary material.

If you are not sure whether your background suffices, please see the instructor. The course is designed for graduate students but may be suitable for advanced undergraduates. Undergraduate students who are interested in taking the course are advised to consult with the instructor before registering.


Teaching Assistant

Alexandra Kolla (akolla [at] illinois [dot] edu) 3222 SC [AK]

Konstantinos Koiliaris (koiliar2 [at] illinois [dot] edu) [KK]


Tuesday 12:30PM - 01:45PM and Thursday 12:30PM - 01:45PM | 1105 SC

Office Hours

Alexandra Kolla - Wednesdays 12:00 @ 3222 SC


# Date Topic Lecture Slides Reading Material
1 T August 25 Introduction to Randomness Slides Miller - Rabin Randomized Primality Testing
2 R August 27 The Probabilistic Method and First Moment Slides Probability and Computing [Sections 6.1, 6.2], The Crossing Number Inequality
3 T September 1 The Second Moment Method Slides Probability and Computing [Section 6.5], Unbiased Estimators [Notes]
4 R September 3 Occupancy Problems, Balls in Bins Slides Probability and Computing [Section 5.1, 5.2]
5 T September 8 Coupon Collector Problems Slides Randomized Algorithms [Section 3.6.1, 3.6.2], 1-D Random Walk
6 R September 10 Expander Graphs Slides Notes on Expanders
7 T September 15 More on Second Moment: Random SAT Slides Random 2-SAT: Results & Problems
8 R September 17 [Hsien] More on Second Moment: Random 2-SAT n/a Mick Gets Some (the Odds Are on His Side)
9 T September 22 Lovasz Local Lemma and more on Random k-SAT Slides Probability and Computing [Section 6.7, 6.8], A constructive proof of the Lovasz Local Lemma
10 R September 24 Probabilistic Method Applications: Min Cut and Fault-tolerant Networks n/a Randomized Algorithms [Section 10.2], Global min-cuts in RNC, and other ramifications of a simple min-out algorithm,
A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
11 T September 29 Chernoff Bounds: Applications Slides Provably good routing in graphs: regular arrays
12 R October 1 Chernoff Bounds: Proofs Slides Probability and Computing [Chapter 4], Chernoff Cheat Sheet
13 T October 6 Chernoff Bounds: Another Application to Routing Slides Probability and Computing [Chapter 4.5.1], Universal Schemes for Parallel Communication, Notes on Chernoff [7.2.3]
14 R October 8 Introduction to Martingales Slides Probability and Computing [Chapter 12.1, 12.4, 12.5], Notes on Martingales
15 T October 13 Martingales and Applications Slides (even more) Notes on Martingales
16 R October 15 Martingales and Applications (cont'd) n/a Probability and Computing [Chapter 12.2 and 12.3]
17 T October 20 [Konstantinos] Topics on LLL and Azuma's n/a
18 R October 22 - - -
19 T October 27 Random Walks and Electrical Networks Slides Notes on Random Walks
20 R October 29 Random Walks and Electrical Networks (contd.), Intro to Markov Chains Slides Notes on Markov Chains, Trailing the Dovetail Shuffle to its Lair
21 T November 3 Markov Chains n/a Notes on Markov Chains, Shuffling Cards and Stopping Times, Mixing of Random Walks and Other Diffusions on a Graph
22 R November 5 Random Matrices n/a A Note on Sums of Independent Random Matrices After Ahlswede-Winter, Trace Inequalities and Quantum Entropy: An Introductory Course
23 T November 10 - - -
24 R November 12 Graph Sparsification by Effective Resistances n/a Graph Sparsification by Effective Resistances
25 T November 17 SDP, Max-Cut and PSRGs n/a Notes on PSRGs, Notes on SDP for Max-Cut, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
26 R November 19 Introduction to Dimension Reduction n/a Notes on Dimension Reduction
27 T November 24 - - -
28 R November 26 - - -
29 T December 1 Metric Embedding in $\ell_1$ n/a Blog Post on Bourgain's Embedding


Homework # Due Homework Solutions
1 [pdf], [tex] September 22nd -
2 [pdf], [tex] October 20th -
3 [pdf], [tex] November 24th -
Final [pdf] December 10th -


There will be a total of 3-4 homeworks.
They can be turned in in groups of up to 3 students. All students in each group get the same grade.

Please do not forget to cite your sources (you will get zero grade if you use material from elsewhere and do not cite the source!)

There will be a take home final exam. You will have one week to submit the exam individually (no teams).
70% homeworks and 30% exam. Extra points may be given for class participation at various occasions.


Part 1: Discrete probability

(approximately over the first 6 weeks)

-Monte Carlo, Las Vegas Algorithms.

-First and Second Moment method, coupon collector problem.

-Probabilistic Method (expanders, Lovasz Local Lemma, Method of conditional probabilities).

-Chernoff Bound and applications.

-Martingales and Azuma.

Part 2:

High-dimensional probability

(approximately over weeks 7-9)

-Bourgain's embedding.

-Curse of Dimensionality, Dimension Reduction.

-Matrix Concentration (Golden-Thompson, Bernstein).

-Random Graph eigenvalues via matrix concentration.

-Spectral Graph Sparsification via Sampling.

Part 3:

Random Walks, Markov Chains

(approximately over weeks 10-12)

-Random Walks: hitting times, cover times etc.

-Markov Chains and Mixing.

-Eigenvalues, Expanders and Mixing.

Part 4:

Advanced Topics

(remaining time)

-Lifts and Expanders, Interlacing Families of Polynomials.

-Stochastic Block Models, Planted Partition Models.

-Other Topics on Random Graphs.