CSE 525: Randomized Algorithms (Spring 2025)

In this course, we study the basics of probabilistic combinatorics with modern applications in the theory of computing.

Administrative Information

Instructor: Shayan Oveis Gharan

Office Hours: Tue 11:30–12:20, Allen Center 636

Lectures: Tue–Thu 10:00–11:20 in ECE 003, additional lectures Fri (Apr 3rd, 24th) 10:00-11:20 ECE 045

Teaching Assistants

• Dante Tjowasi, Office hour: Gates Center 151, Wednesdays, 10-11 am

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

Discussion Board

Assignments

• HW1, html, due April 10
• HW2, html, due April 17
• HW3, html, due May 1
• HW4, html, due May 8
• HW5, html, due May 22

Final Project

Final Project

• 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 Delta+1 Vertex Coloring
• Palette Sparsification Beyond Delta+1 Vertex Coloring
• The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues
• Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlos Bounds Beyond Banaszczyk
• Vizing's Theorem in Near-Linear Time
• 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

Related Materials

• Randomized Algorithms (Nick Harvey)
• Randomness and Computation

Class notes

Schedule