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.1-6.2 from Textbook | |
| 8 | F October 15 | Probabilistic Method, contd. | Chapter 6.3-6.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: 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. |