CS 574, Spring 2021
Randomized Algorithms
Instructor

Timothy Chan
(tmc "at" illinois.edu, office hours: Fri 2:00pm3:00pm on
zoom,
or if you want to meet at a different time, just email me)
Meeting Time

Mon & Wed 9:30am10:45am on zoom
(if you are not officially registered but wants to attend, just email me)
Course Work
 4 or 5 homeworks (problem sets), worth 70% (done in groups of up to 3)
 final exam, worth 30% (between May 10 Mon 2pm and May 12 Wed 2pm,
3 hours duration)
Tentative Topics/Outline
 Introduction: quicksort and quickselect, Rabin and Miller's
primality testing algorithm, complexity classes (ZPP, RP, BPP)
 Random reordering: examples from computational geometry,
AND/OR tree evaluation
 Random sampling: selection again (and
2wise independence and 2point sampling), Clarkson's linear programming algorithm
(and epsilonnets),
Karger, Klein, and Tarjan's MST algorithm,
witness finding, color coding
 More sampling and concentration bounds:
Chernoff, Hoeffding, Azuma (and martingales), further applications
(balls and bins, approximate counting, ...)
 Algebraic methods:
fingerprinting (and SchwarzZippel lemma),
Rabin and Karp's string matching algorithm,
Mulmuley, Vazirani, and Vazirani's parallel
perfect matching algorithm (and isolation lemma)
 Randomized data structures:
skiplist, treap, hashing (2universal, perfect, power of 2 choices, cuckoo, ...)
 Random projection and embeddings: localitysensitive hashing,
dimension reduction (JohnsonLindenstrass), ...
 Random walk and Markov chains: Schöning's kSAT algorithm,
Goel, Kapralov, and Khanna's bipartite perfect matching algorithm for
regular graphs, approximate counting, expanders, ...
 Randomized rounding: MAXSAT/MAXCUT
 Other topics: derandomization (e.g., method of conditional probabilities),
Lovasz local lemma (and Moser and Tardos' algorithm),
randomized online algorithms, sublineartime algorithms, ... (and maybe some of my recent research, if time permits :)
Prerequisites
 Undergraduate algorithms, at the level of CS374
(CS473 is helpful but not required), and sufficient mathematical
maturity (including basic knowledge of probability theory)
Resources
 Motwani and Raghavan's book (1995) is highly recommended and
available online for UIUC students

Sariel's notes from past versions of the course are also recommended
 another book is Mitzenmacher and Upfal (2nd ed., 2017, but apparently not available online)
 other notes online can be found in similar courses elsewhere
(e.g., Tim Roughgarden (Stanford),
Eric Price (UT Austin),
James Aspnes (Yale), ...)
 Campuswire for discussion
(enrollment code: 1803)
Lectures
(Scribbles from class will be provided below.
Lectures will be also recorded, and for registered students, recordings may be accessed at mediaspace. [MR] refers to Motwani and Raghavan's book.
Many papers may be accessed via
UIUC library's proxy bookmarklet.)
 Jan 25: Introduction. Quicksort and quickselect. Primality testing (MillerRabin algorithm). Ref: [MR, Sec 14.6]
 Jan 27: Basic probability review. Randomized complexity classes (ZPP, RP). Ref: [MR, Sec 1.5]
 Feb 1: More randomized complexity classes (BPP).
Adleman's theorem (BPP in P/poly). Random reordering.
 Feb 3: Line segment intersection and trapezoidal decomposition (randomized incremental algorithm by ClarksonShor'89/Mulmuley'88, and Seidel's "backwards analysis"). Ref: [MR, Sec 9.6]
 Feb 8: AND/OR tree evaluation (Snir's algorithm). Yao's principle. Ref: [MR, Sec 2.12.2]
 Feb 10: Random sampling. Median finding (Floyd and Rivest's algorithm).
Ref: [MR, Sec 3.3]
 Feb 15: Median cont'd (pairwise independence, 2point sampling, time/space tradeoffs).
Ref: [MR, Sec 3.33.4; my paper]
 Feb 17: no class (break).
 Feb 22: Min enclosing circle (Clarkson's sampling algorithm). Ref: [MR, Sec 9.10]
 Feb 24
and Mar 1: MST (Karger, Klein, and Tarjan's samplingbased algorithm). Ref: [MR, Sec 10.3] (and backwards analysis)
 Mar 3: Witness finding for Boolean matrix multiplication. Color coding for simple kcycles.
Ref: [MR, Sec 10.1.2] and Alon, Yuster, and Zwick's paper
 Mar 8 and Mar 10: Concentration bounds. Chernoff, Hoeffding, and applications.
Ref: [MR, Sec 4.1] or [Sariel's notes, Ch 7]
 Mar 15
and Mar 17: Applications to approximate counting and approximate volume of unions (Karp and Luby's algorithm). Azuma and martingales (and method of bounded differences).
Ref: [MR, Sec 11.2 and 4.4]
 Mar 22: Algebraic techniques. Matrix multiplication verification (Freivalds), string matching (RabinKarp), SchwartzZippel lemma. Ref: [MR, Sec 7.17.6]
 Mar 24: no class (break).
 Mar 29: Perfect matching (Mulmuley, Vazirani, and Vazirani's parallel algorithm). Isolation lemma. Ref: [MR, Sec 7.3 and 12.4]
 Mar 31: Randomized data structures.
Skip lists. Treaps. Ref: [MR, Sec 8.3 and 8.2]
 Apr 5: Hashing (2universal hash families, perfect hashing). Ref: [MR, Sec 8.4] or
Jeff's notes
 Apr 7: Approximate nearest neighbor search by
localitysensitive hashing. Ref:
original paper by Indyk and Motwani
 Apr 12: JohnsonLindenstrass lemma (dimension reduction, L2 to L1). Ref: Sec 2 of notes by Matousek
 Apr 14: Random walks.
Papadimitriou's 2SAT algorithm, Schöning's 3SAT algorithm.
Ref: [MR, Sec 6.1] and Schöning's paper
 Apr 19: Markov chains, stationary distribution, hitting time.
Ref: [MR, Sec 6.2]
 Apr 21: Perfect matching in regular bipartite graphs (GoelKapralovKhanna). Undirected connectivity in randomized log space.
Ref: Goel et al.'s paper,
[MR, Sec 6.56.6]
 Apr 26: Cover time. Expanders and rapid mixing.
Ref: [MR, Sec 6.7], Hoory, Linial, and Wigderson's survey on expanders
(in particular, Sec 3.1)
 Apr 28: Expanders and probability amplification.
Ref: [MR, Sec 6.8] and Sec 3.23.3 of the above survey
 May 3: Miscellaneous topics. Lovasz Local Lemma and Moser's algorithm.
Ref: [MR, Sec 5.5] and
Lance Fortnow's blog post (or Terry Tao's)
 May 5: Derandomization via method of conditional probabilities (examples: discrepancy and MAXSAT via randomized rounding).
Ref: [MR, Sec 5.6 and 5.2]