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], 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 | - |
| Homework |
|---|
| 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!) |
| 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: 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. |