Subject 
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. 
Prerequisites 
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. 
InstructorTeaching Assistant 
Alexandra Kolla (akolla [at] illinois [dot] edu) 3222 SC [AK] Konstantinos Koiliaris (koiliar2 [at] illinois [dot] edu) [KK]

Times 
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], 1D Random Walk 
6  R September 10  Expander Graphs  Slides  Notes on Expanders 
7  T September 15  More on Second Moment: Random SAT  Slides  Random 2SAT: Results & Problems 
8  R September 17  [Hsien] More on Second Moment: Random 2SAT  n/a  Mick Gets Some (the Odds Are on His Side) 
9  T September 22  Lovasz Local Lemma and more on Random kSAT  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 Faulttolerant Networks  n/a  Randomized Algorithms [Section 10.2], Global mincuts in RNC, and other ramifications of a simple minout algorithm, A Randomized Fully Polynomial Time Approximation Scheme for the AllTerminal 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 AhlswedeWinter, 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, MaxCut and PSRGs  n/a  Notes on PSRGs, Notes on SDP for MaxCut, 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   
Homework 

There will be a total of 34 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!) 
Exams 

There will be a take home final exam. You will have one week to submit the exam individually (no teams). 
Grading 

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: Highdimensional probability (approximately over weeks 79) 
Bourgain's embedding. Curse of Dimensionality, Dimension Reduction. Matrix Concentration (GoldenThompson, Bernstein). Random Graph eigenvalues via matrix concentration. Spectral Graph Sparsification via Sampling.

Part 3: Random Walks, Markov Chains (approximately over weeks 1012) 
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. 