Welcome to Randomized Algorithms CS 134 for Spring 2025.

Lectures: Mondays and Wednesdays, 2 - 3:15pm in Phelps 2510. (Eric Vigoda vigoda@ucsb.edu)
Sections: Thursdays 4-5 or 5-6pm in ILP 3107. (Ajay aj66@ucsb.edu)

Office hours: Eric: Mondays 3:30-4pm and Tuesdays 1:15-2:15pm in HFH 2113 (Eric's office)
Ajay: Mondays and Wednesdays 4-5pm in CSIL in HFH
(Check Ed for last minute OH updates.)

Textbook: Probability and Computing by Michael Mitzenmacher and Eli Upfal [MU]. Available from Amazon or the UCSB bookstore.
Ed Discussion: Join link: https://edstem.org/us/join/EAdn6w. (use your name as in Canvas when enrolling)

Grading scheme:

Homeworks: 70% (out: Wednesdays, due: following Wednesday night) -- submitted via Gradescope. Need to be typed in LaTeX (can use overleaf).
Project: 30%

Preliminary project info posted here

Lecture schedule:

Monday, March 31: Verifying Matrix Multiplication and expected run time of QuickSort
Reading: [MU] Chapters 1.3 and 2.5, and Eric's notes (see Files section)
Wednesday, April 2: Karger's Min-cut algorithm
Reading: [MU] Chapter 1.5 or Eric's old lecture notes
HW 1 will post on Gradescope at 5pm (due: Wed. April 9).
Monday, April 7: Approximation algorithms for Max-Cut and Max-SAT using first moment method and method of conditional expectations
Reading: [MU] Chapters 6.1-6.3
Wednesday, April 9: LP-randomized rounding for (3/4)-approx. alg for Max-SAT
Reading: Eric's lecture notes here or MOOC video LP4
Monday, April 14: Approx alg. via Semidefinite Programming (SDP)
Reading: Eric's notes (in Files) or original [Goemans-Williamson '95] paper
Wednesday, April 16: Chernoff bounds: Application for Data Streaming (Median)
Reading: Eric's notes (in Files)
Monday, April 21: Data Streaming: Number of Distinct Elements
Reading: Eric's notes (in Files) and Amit Chakrabarti's Dartmouth notes
Wednesday, April 23: Proof of Chernoff Bounds
Reading: [MU] Chapter 4
Monday, April 25: Approximate Counting and Sampling
Reading: [MU] Chpt 11.1,11.3; Eric's notes, Chpt 3 of Jerrum
Wednesday, April 27: Intro to Markov Chains
Reading: [MU] Chapter 11.4
(historical sidenote: history of Metropolis alg., see also Wikipedia)
Monday, May 5: Coupling Technique
Reading: [MU] Chapter 12.2
Wednesday, May 7: Glauber Dynamics for Random Colorings
Reading: [MU] Chapter 12.5-12.6
Monday, May 12: Coupling from the Past
Reading: Eric's old lecture notes
Wednesday, May 14: Conductance and Canonical Paths
Reading: [Jerrum] Chapter 5 or [Levin-Peres] Chapter 7.2
Monday, May 19: Random Matchings
Reading: [Jerrum] Chapter 5
Wednesday, May 21: Permanent = Random Perfect Matchings
Reading: see Eric's notes in Files
Monday, May 26: No class - Memorial Day
Wednesday, May 28: Spectral Independence