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 003
Teaching Assistants:
- Ziyun Chen, Office hour: Gates Center 153, Wednesdays 11:00-12:00
Discussion Board
- HW1 due by Thursday April 10th.
- HW2 due by Thursday April 17th.
- HW3 due by Thursday May 1st.
- HW4 due by Thursday May 15th.
- HW5 due by Thursday May 22nd.
- HW6 due by Thursday June 5th.
Assignments
Class Mailing list: cse525a_sp25
Final Project
Suggestions- Optimal Bounds for the k-cut Problem
- Towards optimal two-source extractors and Ramsey graphs
- An exponential improvement for diagonal Ramsey
- On independent sets in random graphs
- Algorithmic barriers from phase transitions"
- Sublinear Algorithms for (Δ+1) Vertex Coloring
- Palette Sparsification Beyond (Δ+1) Vertex Coloring
- The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues
- Cover times, blanket times, and majorizing measures
- Exponential concentration of cover times
- Spectral hypergraph sparsification via chaining
- Negative-Weight Single-Source Shortest Paths in Near-linear Time
- An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles
- Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
- Constructive discrepancy minimization for convex sets
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 (04/01/2025) | 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 (04/03/2025) | Second Moment Method | Chapter 3 of Alon-SpencerKahn-Kalai Conjecture and Phase Transition in Random Graphs | ||
| Lecture 3 (04/08/2025) | Unreliability, DNF Couting | A recent work on unreliability with improved runtime | ||
| Lecture 4 (04/10/2025) | Strong Concentration Bounds, Giant Component in Erdos Reyni graphs | Chapter 4 of Alon-SpencerHardness results on Min Congestion Problem | ||
| (04/15/2025) | No Lecture: Instructor Traveling | |||
| Lecture 5 (04/17/2025) | Lovasz Local Lemma | Chapter 5 of the Alon-Spencer Book Local Lemma and Maximizing Fairness | ||
| Lecture 6 (04/22/2025) | Algorithmic Lovasz Local Lemma | A generalization of Moser-Tardos argument | ||
| Lecture 7 (04/24/2025) | Positive Association and Negative Correlation | Chapter 6 of Alon-Spencer book, Towards a Theory of Negative Dependence | ||
| Lecture 8 (04/29/2025) | 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 (05/06/2025) | Algorithm design with Strongly Rayleigh Distribution | |||
| Lecture 10 (05/08/2025) | Martingales I: Azuma's Inequality | Chapter 7 of Alon-Spencer Book | ||
| Lecture 11 (05/13/2025) | Martingales II: Pipage Rounding | Swap Rounding and Applications | ||
| Lecture 12 (05/15/2025) | Martingales III: Lovett Meka Algorithm | Discrepancy Minimization Using Convex Progreamming | ||
| Lecture 13 (05/20/2025) | Random Walks and Electrical networks | |||
| Lecture 14 (05/22/2025) | 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 15 (05/27/2025) | Matrix Chernoff Bound | Matrix Chernoff bound for SR dist Matrix Chernoff bound for Expander Walks | ||
| Lecture 16 (05/29/2025) | Spectral Sparsification of Graphs | Hypergraph Spectral SparsificationLinear Sized Spectral Sparsifiers Dynamic Spectral Sparsification in Linear Time and Space Effective Resistance Sparsifiers | ||
| Lecture 17 (06/03/2025) | Generic Chaining | |||
| Lecture 18 (06/05/2025) | Hypergraph Sparsification | |||