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
Homeworks
Lectures
- (Sep 4, VG) Introduction, classes FPT and XP, two proofs that
Vertex Cover in FPT. (scribe notes by C.J. Argue)
- (Sep 9, VG) Kernelization techniques for Vertex Cover [Section 2.5] (scribe notes by
Komal Dhull)
- (Sep 11, VG) Reductions for problems in FPT... (scribe notes by
Anish Sevakari)
- (Sep 16, AG) Randomized Methods (scribe notes by
Xiruo Zhang)
- (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.
- (Sep 23, AG) Fast(er) Exponential-time Algorithms (scribe notes by Omar
Alrabiah)
- (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.
- (Sep 30, VG) SERF reductions and the Sparsification Lemma (scribe notes by Aditya Raut)
- (Oct 2, VG) Sparsification Lemma wrap up, 2CNF deletion via Vertex Cover above Matching/LP (scribe notes by Peter Manohar)
- (Oct 7, VG) VC over LP, Fast alorithms for Hamilton Cycle, Zeta and Mobius transforms. (scribe notes by Sai Sandeep)
- (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.
- (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.
- (Oct 16, VG) Integer Linear Programming in Low Dimensions: Endgame
(scribe: Paul Liang)
- (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.
- (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.
- (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.
- (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).
- (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.
- (Nov 6, AG) Geometric Algorithms II: finishing k-means
(scribe notes by Jackson Abascal)
- Handwritten notes. (same as the previous lecture).
- (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
- (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
- (Nov 18, VG) (Scribe notes by Jasper Hugunin)
- Biclique hardnes wrapup; Nearest Codeword and Minimum Distance Codeword
- (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.
- (Nov 25, AG) Using (Euclidean/Doubling) Dimension as a Parameter:
TSP and Spanners (Scribe notes by Bailey Flanigan)
- (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
- (Dec 4, AG) Cut problems and Wrapup (Scribe notes by Dravyansh Sharma)
Maintained by Anupam Gupta and Venkat Guruswami.