In this course, we study the basics of probabilitic combinatorics with some mondern applciations in theory of computing.
Administrative Information
Instructor: Shayan Oveis Gharan
Office Hours: Tue 11:30-12:10, Allen Center 636
Lectures: Tue - Thu 10:00 - 11:20 in ECE 031
Teaching Assistants:
- Dorna Abdolazimi, Office hour: Fridays 3:30-4:20 at Gates Center 374
- Farzam Ebrahimnejad
Discussion Board
Assignments
The assignment file will be updated weekly. Assignment.Class Mailing list: cse525a_sp23
Common Knowledge
Related Materials
Similar courses at other schools- Randomized Algorithms by Nick Harvey
- Randomness and Computation by Alistair Sinclair
- The Probabilistic Method by Noga Alon and Joel Spencer
- Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
- Random Graphs by Alan Frieze
- Markov Chains and Mixing Times by David Levin, Yuval Peres, Elizabeth Wilmer
Tentative Schedule:
| Lecture | Topic | Notes | Reading | Files |
|---|---|---|---|---|
| Lecture 1 (03/28/2023) | Introduction, The probabilistic Method, Linearity of Expectations | Chapters 1,2 of Alon-Spencer Inapproximability of Max 3SATA 7/8 approximation Alg for Max 3SAT | ||
| Lecture 2 (03/30/2023) | Second Moment Method | Chapter 3 of Alon-SpencerKahn-Kalai Conjecture and Phase Transition in Random Graphs | ||
| Lecture 3 (04/04/2023) | Unreliability, DNF Couting | A recent work on unreliability with improved runtime | ||
| Lecture 4 (04/06/2023) | Strong Concentration Bounds, Routing with minimum Congestion | Hardness results on Min Congestion Problem | ||
| Lecture 5 (04/11/2023) | Lovasz Local Lemma | Chapter 5 of the Alon-Spencer Book Local Lemma and Maximizing Fairness | ||
| Lecture 6 (04/13/2023) | Algorithmic Lovasz Local Lemma | A generalization of Moser-Tardos argument | ||
| Lecture 7 (04/18/2023) | Negative Correlationand Concentration | Chapter 6 of Alon-Spencer book, Towards a Theory of Negative Dependence | ||
| Lecture 8 (04/20/2023) | Intro to Strongly Rayleigh Distributions | Negtative Dependence and Geometry of Polynomials Concentration of Lipshitz functions of SR Distributions On Efficient Sampling SR Distributions | ||
| Lecture 9 (04/25/2023) | Martingales I: Azuma's Inequality | Chapter 7 of Alon-Spencer Book | ||
| Lecture 10 (04/27/2023) | Martingales II: Pipage Rounding | Swap Rounding and Applications | ||
| Lecture 11 (05/02/2023) | Random Walks and Electrical networks | |||
| Lecture 12 (05/04/2023) | Hitting Time and Cover Time | Random Walks and Effective Resistance Survey Fast Generation of Random Spanning Trees using Eff Resistnce Metric A Deterministic Algorithm to Estimate Covertime | ||
| Lecture 13 (05/09/2023) | Matrix Chernoff Bound | Matrix Chernoff bound for SR dist Matrix Chernoff bound for Expander Walks | ||
| Lecture 14 (05/11/2023) | Spectral Sparsification of Graphs | Hypergraph Spectral SparsificationLinear Sized Spectral Sparsifiers Dynamic Spectral Sparsification in Linear Time and Space Effective Resistance Sparsifiers | ||
| Lecture 15 (05/16/2023) | Intro to Markov Chain Mixing Time | |||
| Lecture 16 (05/18/2023) | Coupling Method: Counting Coloring | Riffle SHuffle | ||
| Lecture 17 (05/23/2023) | Copuling Continued | Improved Bounds for Sampling Colorings Coupling with the Stationary Distribution | ||
| Lecture 18 (05/25/2023) | Bounding Mixing Tie by Poincare Constant | Counting Perfect Matchings in Bipartite Graphs MCMC for Sampling SR Distributions MCMC for the Ising Model MCMCM for Sampling Bases of Matroids | ||
| Lecture 19 (05/25/2023) | Sampling Matchings in General Graphs |