CSE 525: Randomized Algorithms (Spring 2023)

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:

Course evaluation: Homework (~80%), Final project (~20%).
Discussion Board


The assignment file will be updated weekly. Assignment.

Class Mailing list: cse525a_sp23

Common Knowledge

Related Materials

Similar courses at other schools Here is a list of related books
Inclass Notes in Scribble.

Tentative Schedule:

Lecture Topic Notes Reading Files
Lecture 1
Introduction, The probabilistic Method,
Linearity of Expectations
pdf Chapters 1,2 of Alon-Spencer
Inapproximability of Max 3SAT
A 7/8 approximation Alg for Max 3SAT
Lecture 2
Second Moment Method pdf Chapter 3 of Alon-Spencer
Kahn-Kalai Conjecture and Phase Transition in Random Graphs
Lecture 3
Unreliability, DNF Couting pdf A recent work on unreliability with improved runtime
Lecture 4
Strong Concentration Bounds, Routing with minimum Congestion pdf Hardness results on Min Congestion Problem
Lecture 5
Lovasz Local Lemma pdf Chapter 5 of the Alon-Spencer Book
Local Lemma and Maximizing Fairness
Lecture 6
Algorithmic Lovasz Local Lemma pdf A generalization of Moser-Tardos argument
Lecture 7
Negative Correlationand Concentration pdf Chapter 6 of Alon-Spencer book,
Towards a Theory of Negative Dependence
Lecture 8
Intro to Strongly Rayleigh Distributions pdf Negtative Dependence and Geometry of Polynomials
Concentration of Lipshitz functions of SR Distributions
On Efficient Sampling SR Distributions
Lecture 9
Martingales I: Azuma's Inequality pdf Chapter 7 of Alon-Spencer Book
Lecture 10
Martingales II: Pipage Rounding pdf Swap Rounding and Applications
Lecture 11
Random Walks and Electrical networks pdf
Lecture 12
Hitting Time and Cover Time pdf Random Walks and Effective Resistance Survey
Fast Generation of Random Spanning Trees using Eff Resistnce Metric
A Deterministic Algorithm to Estimate Covertime
Lecture 13
Matrix Chernoff Bound pdf Matrix Chernoff bound for SR dist
Matrix Chernoff bound for Expander Walks
Lecture 14
Spectral Sparsification of Graphs pdf Hypergraph Spectral Sparsification
Linear Sized Spectral Sparsifiers
Dynamic Spectral Sparsification in Linear Time and Space
Effective Resistance Sparsifiers
Lecture 15
Intro to Markov Chain Mixing Time pdf
Lecture 16
Coupling Method: Counting Coloring pdf Riffle SHuffle
Lecture 17
Copuling Continued pdf Improved Bounds for Sampling Colorings
Coupling with the Stationary Distribution
Lecture 18
Bounding Mixing Tie by Poincare Constant pdf Counting Perfect Matchings in Bipartite Graphs
MCMC for Sampling SR Distributions
MCMC for the Ising Model
MCMCM for Sampling Bases of Matroids
Lecture 19
Sampling Matchings in General Graphs pdf