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 (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 (scribe notes by Tian Luo)

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

  20. (Nov 11, VG)

  21. (Nov 13, VG) Scribe notes by Max Bender

  22. (Nov 18, VG) (Scribe notes by Jasper Hugunin)

  23. (Nov 20, VG) Odd Hitting Set hardness; A Sieving Algorithm for the Shortest Vector Problem (Scribe notes by Praneeth Kacham)
    • The Ajtai-Kumar-Sivakumar paper.
    • Oded Regev's notes.

  24. (Nov 25, AG) Using (Euclidean/Doubling) Dimension as a Parameter: TSP and Spanners (Scribe notes by Bailey Flanigan)

  25. (Dec 2, JL) Algorithms for Planar Graph Problems: Bidimensionality

  26. (Dec 4, AG) Cut problems and Wrapup (Scribe notes by Dravyansh Sharma)

Maintained by Anupam Gupta and Venkat Guruswami.