CS 574, Spring 2021

Randomized Algorithms

Instructor

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

Meeting Time

• Mon & Wed 9:30am-10: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)
  • Homework 1 (corrected version 2/9) (due Feb 22 Mon 5pm)
  • Homework 2 (corrected version 3/8) (due March 10 Wed 5pm)
  • Homework 3 [.tex] (due March 31 Wed 5pm)
  • Homework 4 [.tex] (due April 19 Mon 5pm)
  • Homework 5 [.tex] (due April 30 Fri 5pm)
  • (comments on past HW problems)
  • submit homework on Gradescope (entry code WYJ4X2) (note: if you use a different alias or email address on gradescope, just let me know by email...)
• 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 re-ordering: examples from computational geometry, AND/OR tree evaluation
• Random sampling: selection again (and 2-wise independence and 2-point sampling), Clarkson's linear programming algorithm (and epsilon-nets), 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 Schwarz-Zippel lemma), Rabin and Karp's string matching algorithm, Mulmuley, Vazirani, and Vazirani's parallel perfect matching algorithm (and isolation lemma)
• Randomized data structures: skip-list, treap, hashing (2-universal, perfect, power of 2 choices, cuckoo, ...)
• Random projection and embeddings: locality-sensitive hashing, dimension reduction (Johnson-Lindenstrass), ...
• Random walk and Markov chains: Schöning's k-SAT algorithm, Goel, Kapralov, and Khanna's bipartite perfect matching algorithm for regular graphs, approximate counting, expanders, ...
• Randomized rounding: MAX-SAT/MAX-CUT
• Other topics: derandomization (e.g., method of conditional probabilities), Lovasz local lemma (and Moser and Tardos' algorithm), randomized online algorithms, sublinear-time 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 (Miller-Rabin 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 re-ordering.
• Feb 3: Line segment intersection and trapezoidal decomposition (randomized incremental algorithm by Clarkson-Shor'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.1-2.2]
• Feb 10: Random sampling. Median finding (Floyd and Rivest's algorithm). Ref: [MR, Sec 3.3]
• Feb 15: Median cont'd (pairwise independence, 2-point sampling, time/space tradeoffs). Ref: [MR, Sec 3.3-3.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 sampling-based algorithm). Ref: [MR, Sec 10.3] (and backwards analysis)
• Mar 3: Witness finding for Boolean matrix multiplication. Color coding for simple k-cycles. 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 (Rabin-Karp), Schwartz-Zippel lemma. Ref: [MR, Sec 7.1-7.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 (2-universal hash families, perfect hashing). Ref: [MR, Sec 8.4] or Jeff's notes
• Apr 7: Approximate nearest neighbor search by locality-sensitive hashing. Ref: original paper by Indyk and Motwani
• Apr 12: Johnson-Lindenstrass 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 (Goel-Kapralov-Khanna). Undirected connectivity in randomized log space. Ref: Goel et al.'s paper, [MR, Sec 6.5-6.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.2-3.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 MAX-SAT via randomized rounding). Ref: [MR, Sec 5.6 and 5.2]