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. 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. 
Instructor 
Alexandra Kolla (alexandra.kolla [at] colorado [dot] edu) 122 ECEE [AK]

Times 
Fridays 1:50 4:20 pm  ECES 114 
Office Hours 
Alexandra Kolla  TBD 
#  Date  Topic  Lecture Slides  Reading Material 

1  F August 27  Introduction to Randomness  Slides  Miller  Rabin Randomized Primality Testing 
2  F September 3  Events and Probability  Slides  Chapter 1 from Textbook 
3  F September 10  Random Variables and Expectation  Chapter 2 from Textbook  
4  F September 17  Moments, Deviations  Chapter 3 from Textbook  
5  F September 14  Chernoff Bounds  Chapter 4 from Textbook  
6  F October 1  Balls in Bins  Chapter 5 from Textbook  
7  F October 8  Probabilistic Method  Chapter 6.16.2 from Textbook  
8  F October 15  Probabilistic Method, contd.  Chapter 6.36.7 from Textbook  
9  F October 21  Lovasz Local Lemma, SDP for Max Cut.  Chapter 6 from Textbook and this paper  
10  F October 29  Lovasz Local Lemma, SDP for Max Cut cntd.  MaxCut notes and Constructive LLL paper  
11  F November 5  Markov Chains  Chapter 7 from Textbook  
12  F November 12  Random walks on graphs and eigenvalues  Look at these notes  
13  F November 19  Martingales  Chapter 10 from Textbook  
Homework #  Due  Homework Solutions 

HW 1  September 17   
HW 2  September 24   
HW 3  October 1   
HW 4  October 8   
HW5  October 21   
HW6  October 29   
HW7  November 5   
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. 