CS1.406 Advanced Algorithms (Spring 2025)

Published

January 1, 2025

Announcements

  • Teaching assistants:
  • Schedule: Monday and Friday, 11:40 – 13:05
  • Classroom: H204

Lectures

Lecture 1: Verifying Matrix Multiplication

References:

  1. Section 1.3 of Mitzenmacher-Upfal

Lectures 2, 3 & 4: PIT and Parallel Algorithms for Matching

References:

  1. Notes from UWash
  2. Mulmuley Vazirani Vazirani paper (Lemma 3)
  3. New (stronger) proof for Isolation Lemma by Noam Ta-Shma

Lecture 5: Chernoff Bound

References:

  1. Section 4.1 till 4.3 of Mitzenmacher & Upfal

Lectures 5 & 6: Approximate Counting

References:

  1. Sections 11.1 and 11.2 of Motwani-Raghavan
  2. Sections 10.1 and 10.2 of Mitzenmacher-Upfal
  3. Suggested reading: Section 10.3 of Mitzenmacher-Upfal (optional)

Lectures 7 & 8: k-path Problem

References:

  1. Course notes from MIT course on Fine Grained Complexity - 1
  2. MIT course on Fine Grained Complexity - 2
  3. An expository of k-path

Lecture 9: k-3D Matching

References:

  1. Review article by Koutis and Williams

Lecture 10: Counting Perfect Matchings

References:

  1. Bax, E., & Franklin, J. (1996). “A finite-difference sieve to count paths and cycles by length”. Information Processing Letters, 60(4), 171-176.
  2. Björklund, A., & Williams, R. (2019). “Counting Perfect Matchings in O(n²ⁿ) Time”. Proc. ICALP 2019.

Lecture 11: Dissimilar Vectors

References:

  1. Section 2 of Bjorklund-Williams

Lectures 12, 13, 14 & 15

References:

  1. Chapter 7 of Mitzenmacher-Upfal

Lectures 15 & 16: MaxSAT

References:

  1. Sections 6.1 till 6.3 of Mitzenmacher-Upfal

Lecture 17: MinCut & RandQS

References:

  1. Chapter 1 of Mitzenmacher-Upfal

Lecture 18: Coupon Collector Problem & Balls and Bins

References:

  1. Sections 2.4 and 5.2 of Mitzenmacher-Upfal

Lectures 19-23: Hashing

References:

  1. Sections 15.1 and 15.3 of Mitzenmacher-Upfal
  2. Yossi Matias’ notes on FKS hashing
  3. More resources

Additional Resources

Main Textbooks
Key Papers
Course Materials