15-859FF: Coping with intractability: parameterized and fast-exponential algorithms, Fall 2019

Lecturers: Anupam Gupta, GHC 7203, Venkat Guruswami, GHC 7211
TA: Jason Li.

Office hours:
Anupam: Tue 5-6pm, GHC 7203
Venkat: Mondays 4-5pm, GHC 7211 (no office hours Sep 16,23)
Jason: Wednesdays 1:30-2:30pm, GHC 5109.

Location: GHC 4211, MW 10:30-11:50
Piazza: here




  1. (Sep 4, VG) Introduction, classes FPT and XP, two proofs that Vertex Cover in FPT. (scribe notes by C.J. Argue)

  2. (Sep 9, VG) Kernelization techniques for Vertex Cover [Section 2.5] (scribe notes by Komal Dhull)

  3. (Sep 11, VG) Reductions for problems in FPT... (scribe notes by Anish Sevakari)

  4. (Sep 16, AG) Randomized Methods (scribe notes by Xiruo Zhang)

  5. (Sep 18, AG) Iterative Compression (scribe notes by Amulya Musipatla)

  6. (Sep 23, AG) Fast(er) Exponential-time Algorithms (scribe notes by Omar Alrabiah)

  7. (Sep 25, AG) Inclusion-Exclusion and Longest Path again (scribe notes by Zhen Zhou)

  8. (Sep 30, VG) SERF reductions and the Sparsification Lemma (scribe notes by Aditya Raut)

  9. (Oct 2, VG) Sparsification Lemma wrap up, 2CNF deletion via Vertex Cover above Matching/LP (scribe notes by Peter Manohar)

  10. (Oct 7, VG) VC over LP, Fast alorithms for Hamilton Cycle, Zeta and Mobius transforms. (scribe notes by Sai Sandeep)

  11. (Oct 9, AG) Integer Linear Programming in Low Dimensions: Intro, 2-d case, Lattices (unedited scribe notes by Misha Ivkov)

  12. (Oct 14, AG) Integer Linear Programming in Low Dimensions: the LLL algorithm for Basis Reduction (unedited scribe notes by Rhea Jain)

  13. (Oct 16, VG) Integer Linear Programming in Low Dimensions: Endgame (scribe: Paul Liang)

  14. (Oct 21, JL) Planar Graphs and Planar Separators (scribe notes by Rudy Zhou)

  15. (Oct 23, JL) New Proofs of the Planar Separator Theorem (scribe notes by Hoon Oh)

  16. (Oct 28, JL) Treewidth, Pathwidth, and Algorithms (scribe notes by Sean Zhang)

  17. (Oct 30, JL) Treewidth, Pathwidth, and Algorithms II (scribe notes by Brian Zhang)

  18. (Nov 4, AG) Geometric Algorithms I: k-means (unedited scribe notes by Tian Luo)

  19. (Nov 6, AG) Geometric Algorithms II: finishing k-means (scribe: Jackson Abascal)

  20. (Nov 11, VG)

  21. (Nov 13, VG)

Maintained by Anupam Gupta and Venkat Guruswami.