CS 574: Randomized Algorithms, Fall 2025

Course Summary

Basic and advanced concepts in the design and analysis of randomized algorithms. Sampling; concentration inequalities such as Chernoff-Hoeffding bounds; probabilistic method; random walks, dimension reduction; entropy; martingales and Azuma's inequality; derandomization. Randomized algorithms for sorting and searching; graphs; geometric problems. Basics of pseudorandomness and randomized complexity classes. The actual contents will vary a bit from semester to semester.

Administrative Information

Lectures: 9.30-10.45am on Wed and Fri. Siebel Center 0216.

Instructor:  Chandra Chekuri, 3228 Siebel Center, (chekuri at)

Office Hours (Chandra): Friday 1-2pm in 3228 Siebel, or by appointment

Teaching Assistant:  Rhea Jain (rheaj3 at)

Office Hours (Rhea): Tuesday 2:30-3:30pm, Siebel lower level (open whiteboard area)

Grading Policy: 50% Homework (5 biweekly), 2 x 15% Midterms, 20% final project

Attendance policy: at least 65% of lectures for a grade. The revolution will not be televised, it will be live.

Prerequisites: According to the course catalog: one of CS 473, CSE 414, or MATH 473; and one of MATH 461, MATH 463 or STAT 400. Or equivalent courses from elsewhere. Consult the instructor if you have questions.

Mental health support at UofI: Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University's resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.
Counseling Center: 217-333-3704, 610 East John Street, Champaign, IL 61820
McKinley Health Center: 217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801
University wellness center
Please do not hesitate to contact the instructor if you need help or assistance.

Student code: All students are expected to be aware of the university's student code, in particular the academic integrity policies

CS Code of Conduct: See here for important information on the code of conduct guidelines of the Siebel School of CS.

References

Electronic versions of several books from Cambridge University, Springer, Wiley and other publishers are available free to Univ of Illinois students via the library.

 

 

Ed (sign up at link), Gradescope (7X756Y)  


Homework

Lectures

  • Lecture 1: 8/27/2025, Introduction, Randomized Quick Sort, Markov'e inequality, Max-Cut
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Randomized Quick Sort is covered in all books/notes
    • Additional reading: Randomized Quick Selection, Reverse Markov Inequality

  • Lecture 2: 8/29/2025, Karger's random contraction for min-cut, Karger-Stein variation
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Motwani Raghavan Chapter 1, Aspens/Sariel/Kent notes
    • Additional reading: Galton-Watson process (wikipedia), some notes
    • David Karger's influential thesis

  • Lecture 3: 9/03/2025, Polynomial Identity Testing, Schwartz-Zippel Lemma, Applications to Matchings

  • Lecture 4: 9/05/2025, Chebyshev and Chernoff bounds, applications to max load in balls and bins etc
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Slides from a previous course
    • Chapter 4 of Motwani-Raghavan book or Mitzenmacher/Upfal book, Chapter 5 of Aspnes notes, Chapter 13 of Sariel's notes, ...
    • Sariel Har-Peled's Chernoff cheat sheet

  • Lecture 5: 9/09/2025, Chernoff bounds continued, application to congestion minimization, random walk on the line
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Chapter 5 in Motwani-Raghavan for congestion minimization
    • Chapter 13 of Sariel's notes, especially for the additive Chernoff bound
    • Sariel Har-Peled's Chernoff cheat sheet

  • Lecture 6: 9/12/2025, Dimensionality Reduction and JL Lemma, Intro to pairwise independence
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • For dimensionality reduction, Chapter 23 in Nick Harvey's book, Chapter 24 of Sariel's notes, Chapter 9 in Kent's notes
    • For pairwise independence, Sec 3.5 in Vadhan's pseudorandomness book, Chapter 7 in Sariel's notes

  • Lecture 7: 9/17/2025, t-wise independence and Hashing
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • MR Chapter 8, MU Chapter 5, Aspnes, Sariel, Kent's notes
    • For t-wise independence, Sec 3.5 in Vadhan's pseudorandomness book, Chapter 7 in Sariel's notes
    • Mikkel Thorup's article on hashing
    • A nice introduction to finite fields, and notes

  • Lecture 8: 9/19/2025, Linear Probing based Hashing
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Kent's notes and references therein

  • Lecture 9: 9/24/2025, Intro to streaming, distinct element estimation, amplification via variance reduction and median estimator
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Slides and resources from course on big data (see lectures 1, 5, 6 in particular)
    • Amit Chakrabarti's lecture notes on streaming/sketching
    • Chapter 8 from Kent's notes from Spring 2024
    • Chapter 13 from Nick Harvey's book 1

  • Lecture 10: 9/24/2025, CVM algorithm for distinct elements, AMS algorithms for F_k, F_2
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • For AMS estimators, slides and resources from course on big data (see lecture 7 in particular)
    • For CVM algorithm: Chapter 8 from Kent's notes from Spring 2025
    • Vinod Variyam's page has links to press for CVM algorithm including Don Knuth's note, Quanta article, etc
    • Chapter 13 from Nick Harvey's book 1

  • Lecture 11: 10/1/2025, Heavy Hitters, CountMin and Count Sketches

  • Lecture 12: 10/3/2025, DNF Counting and Unreliability estimation in graphs
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Chapter 11 of Motwani-Raghavan and also Mitzenmacher-Upfal, various lecture notes etc
    • Lecture was mostly based off on notes from Oveis-Gharan's class
    • Karger's paper on unreliability estimation. There have been several recent developments on faster algorithms; see paper

  • Lecture 13: 10/8/2025, Introduction to Markov Chains, Page Rank

  • Lecture 14: 10/10/2025, Random walks in undirected graphs, basics
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Chapter 11 of Motwani-Raghavan and also Mitzenmacher-Upfal

  • Lecture 15: 10/15/2025, Random walks in undirected graphs and electrical networks
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Chapter 20 of Kent's notes
    • Doyle and Snell's well-known book
    • Chapter 11 of Motwani-Raghavan and also Mitzenmacher-Upfal

  • Lecture 16: 10/15/2025, Convergence of random walks in undirected graphs via spectral analysis
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Chapter 21 of Kent's notes
    • Lap Chi Lau's notes/book on spectral graph theory

  • Lecture 17: 10/22/2025, Expanders and random walks
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Chapter 11 of Motwani-Raghavan and also Mitzenmacher-Upfal
    • Chapter 34 of Sariel's notes, Chapter 24 of Kent's notes
    • David Ellis's exposition of Bollobas proof on random d-regular graphs and expansion
    • Expander graphs survey by Hoory, Linial and Widgderson
    • Lap Chi Lau's notes/book on spectral graph theory

  • Lecture 18: 10/24/2025, Negative Correlation, Chernoff bound, and an application to max k-coverage
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Shayan Oveis-Gharan's notes (Lecture 7, 8 etc), Chakrabarty's notes on pipage rounding for coverage
    • Srinivasan's paper on randomized pipage rounding, and generalizations in Gandhi et al paper and CVZ paper
    • A survey talk by Srinivasan on dependent rounding

  • Lecture 19: 10/29/2025, Martingales, Azuma's inequality and some applications
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Shayan Oveis-Gharan's notes (Lecture 10)
    • Mitzenmacher-Upfal Chapter 13

  • Lecture 20: 10/31/2025, Swap rounding and negative correlation
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Shayan Oveis-Gharan's notes (Lecture 11)
    • Paper on swap rounding (see Lemma 4.1 for proof of negative correlation)
    • Vondrak's note on concentration of submodular functions via independent rounding
    • A survey article on concentration inequalities by Boucheron, Lugosi, Bousquet and a book by the same authors

  • No lectures due to instructor travel: 11/05/2025 and 11/07/2025

  • Lecture 21: 11/12/2025, Lovasz Local Lemma and Applications
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Valiant-Wooters (Stanford) notes
    • Shayan Oveis-Gharan's notes (Lecture 5)
    • Mitzenmacher-Upfal Chapter 6, Alon-Spencer Chapter 5

  • Lecture 22: 11/14/2025, Algorithmic Lovasz Local Lemma
    • Kent's notes (Chapter 17)
    • Moser-Tardos paper
    • Shayan Oveis-Gharan's notes (Lecture 6)
    • Valiant-Wooters (Stanford) notes
    • Mitzenmacher-Upfal Chapter 6, Alon-Spencer Chapter 5

  • Lecture 23: 11/19/2025, VC-dimension and \epsilon-approximation
    • Tablet notes, AI converted version (not checked, use with abundance of caution)
    • Kent's notes (Chapter 13)
    • Sariel Har-Peled's notes (Chapters 38 and 39)

  • Lecture 24: 11/21/2025, Intro to PAC Learning

  • Lecture 25: 12/03/2025, Primality Testing