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

Announcements

• Course policies, and other information that were moved off the main page.
• Lecture schedule, and scribe signup sheet.
• HW0 released; due on Sept 6.

Homeworks

• Homework 0 (due Friday, September 6)
• Homework 1 (due Thursday, September 26)
• Homework 2 (due Sunday, October 13)
• Homework 3 (due Thursday, October 31)
• Homework 4 (due Wednesday, November 20)
• Homework 5 (due Friday, December 6)

Lectures

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)
• We loosely follow Chapter 5 of the book; here are handwritten notes.
• The original Monien and Bodlaender papers for Longest Path, and the Alon, Yuster, Zwick color coding paper.
• The Becker, Bar-Yehuda, Geiger randomized algorithm for FVS.


5. (Sep 18, AG) Iterative Compression (scribe notes by Amulya Musipatla)
• We loosely follow Chapter 4 of the book; here are handwritten notes.
• The original Reed, Smith, and Vetta paper on Odd Cycle Transversal that introduced the technique.
  We won't cover it, but it's a very nice and short paper, in case you are interested in reading it.


6. (Sep 23, AG) Fast(er) Exponential-time Algorithms (scribe notes by Omar Alrabiah)
• Handwritten notes.
• Two papers that derandomize Schoening's original paper: by Dantsin et al., and by Moser and Scheder.


7. (Sep 25, AG) Inclusion-Exclusion and Longest Path again (scribe notes by Zhen Zhou)
• Handwritten notes for the inclusion-exclusion part, and some older notes on the $2^k$ time $k$-path algorithm.


8. (Sep 30, VG) SERF reductions and the Sparsification Lemma (scribe notes by Aditya Raut)
• The Impagliazzo-Paturi-Zane paper.


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)
• Bjorklund's algorithm for undirected Hamilton cycle.


11. (Oct 9, AG) Integer Linear Programming in Low Dimensions: Intro, 2-d case, Lattices (unedited scribe notes by Misha Ivkov)
• Handwritten notes.
• We loosely followed notes by Thomas Rothvoss; these in turn cite notes by Oded Regev and Chris Peikert.
• The history of these techniques is from this book on the LLL Basis Reduction Algorithm.


12. (Oct 14, AG) Integer Linear Programming in Low Dimensions: the LLL algorithm for Basis Reduction (scribe notes by Rhea Jain)
• Handwritten notes (same as for Lec 11).
• Basis reduction starts with Lagrange and Gauss, see this book by Scharlau and Opolka.


13. (Oct 16, VG) Integer Linear Programming in Low Dimensions: Endgame (scribe: Paul Liang)
• Section 2 of Lenstra's original paper for algorithmic version of (weaker form of) John's ellipsoid theorem.


14. (Oct 21, JL) Planar Graphs and Planar Separators (scribe notes by Rudy Zhou)
• Handwritten notes.
• We loosely follow the first two pages of these notes by Jeff Erickson.
• The dynamic programming algorithm is inspired by the dynamic programming algorithm on treewidth decomposition technique that we will see in a later lecture.


15. (Oct 23, JL) New Proofs of the Planar Separator Theorem (scribe notes by Hoon Oh)
• Handwritten notes (same notes as last lecture). We did not have time to cover the other proof which uses the circle packing theorem.
• We loosely follow the first three pages of these notes by Christian Sommer.
• The cute proof via the circle packing theorem (that we did not have time to cover in class) is in these notes by Jeff Erickson.


16. (Oct 28, JL) Treewidth, Pathwidth, and Algorithms (scribe notes by Sean Zhang)
• Handwritten notes from old class.
• Chapter 7 of Cygan textbook is a great introduction to treewidth. We covered Sections 7.1 through 7.3.


17. (Oct 30, JL) Treewidth, Pathwidth, and Algorithms II (scribe notes by Brian Zhang)
• Handwritten notes for planar graphs have treewidth O(sqrt(n)*log n).


18. (Nov 4, AG) Geometric Algorithms I: k-means (scribe notes by Tian Luo)
• Handwritten notes.
• The Jaiswal Kumar Sen paper.
• Arthur and Vassilvitskii's paper on k-means++.
• The Inaba Katoh and Imai paper with the sampling lemma, and also the exact $n^{O(kd}}$ algorithm.


19. (Nov 6, AG) Geometric Algorithms II: finishing k-means (scribe notes by Jackson Abascal)
• Handwritten notes. (same as the previous lecture).


20. (Nov 11, VG)
• Weighted circuit satisfaibility and W-hierarchy; Clique and Hitting Set; More W[1]-hardness: Balanced Separator and List Coloring low-treewidth graphs


21. (Nov 13, VG) Scribe notes by Max Bender
• Four major FPT questions and their current status (Biclique, Multicut, Directed FVS, Code minimum distance); Randomized parameterized reduction from Clique to Biclique


22. (Nov 18, VG) (Scribe notes by Jasper Hugunin)
• Biclique hardnes wrapup; Nearest Codeword and Minimum Distance Codeword


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)
    • Handwritten notes.
    • The Arora and Mitchell papers.
    • The Rao-Smith paper from 1998.
    • A proof of the sparse spanners result for doubling metrics.
    • A good treatment appears in the Williamson-Shmoys book.


25. (Dec 2, JL) Algorithms for Planar Graph Problems: Bidimensionality
• Handwritten notes;
• Graph Minors: Section 6.3 of Cygan textbook
• Bidimensionality: Section 7.7 of Cygan textbook


26. (Dec 4, AG) Cut problems and Wrapup (Scribe notes by Dravyansh Sharma)
• Handwritten notes; we mostly follow the book Chapter 8.
• The original Marx paper on important cuts (and multiway cut), and the two papers (Marx and Razgon, Bosquet Daligault Thomasse) showing Multicut in FPT.
• Chen, Liu, Lu, O'Sullivan and Razgon showed that Directed Feedback Vertex Set is in FPT.