Fine-Grained and Parameterized Complexity


Instructor: Adam Polak

Tuesdays 10-12 – Open problems (zoom)
Thursdays 9-13 – Exercise sessions and lectures (room CM-09, or zoom)

Write to [email protected] to subscribe to updates (e.g. zoom links).

The fields of Fine-Grained Complexity and Fixed Parameter Tractability go beyond the simplistic distinction between polynomial time and NP-hard problems, and prove more refined lower and upper bounds on running times of algorithms for certain problems.

Have you wondered if the simple quadratic time algorithm for Edit Distance, which you learned in an introductory lecture on dynamic programming, can be improved upon? Or, if the NP-hard Vertex Cover problem can nonetheless be solved efficiently in some special cases?

In this course we will cover key hypotheses of fine-grained complexity, numerous reductions – often between seemingly distant problems – and algorithmic techniques that enable surprising improvements. The course will be research-oriented.

There will be no exam. Your grade will be based on:

  • Problems you solve and present during exercise sessions or submit in writing.
  • Presentation you give at the end of the semester on a paper you read or your own research on a topic related to the course. Details on the presentations will be announced at the end of March.

The course is worth 4 credits.

This is an advanced course, meant for PhD students and ambitious Master’s students interested in theoretical computer science. There are no formal prerequisites, but you will need some basic knowledge in algorithms and computational complexity, in particular good familiarity with the concepts of polynomial-time reductions and NP-hardness.

(The list is subject to change, suggestions are welcome)

  1. Parameterized complexity of Vertex Cover, branching, kernelization
  2. Color coding technique, algorithms for Longest Path and Subset Sum
  3. Iterative compression technique, Feedback Vertex Set
  4. Treewidth: definition, dynamic programming, bidimensionality, lower bounds
  5. (Strong) Exponential Time Hypothesis and Sparsification Lemma
  6. Orthogonal Vectors, lower bounds for diameter approximation and Edit Distance
  7. All-Pairs Shortest Paths and problems equivalent under subcubic reductions
  8. Unweighted APSP, Seidel’s and Zwick’s algorithms
  9. Boolean Matrix Multiplication and Approximate Pattern Matching
  10. 3SUM and Convolution 3SUM equivalence, Triangle Listing lower bounds
  11. Zero Triangle, reductions from 3SUM and APSP, hardness of Set Disjointness
  12. (min,+)-convolution, reductions to 3SUM and APSP, equivalence with Knapsack
  13. (min,max)-product and APSP approximation
  14. OMv-Hypothesis and lower bounds for dynamic problems
  15. Distributed PCP framework for approximation lower bounds


You should choose either:

  • to work on an open problem of your choice (can be a toy problem, not necesarily a publishable result); or
  • to read a recent paper related (at least loosely) to the topics of the course.

If you opt for the second option, you are free to chose a paper by yourself, but below you can find a list of suggestions.

You will give two presentations:

  • on 29th of April, 10-15 minutes, introducing the topic, and how you plan to approach it; and
  • on 3rd of June, 20-30 minutes, presenting a result (yours or from the paper you read).

You should email you choice at least one weak before the first presentation, i.e., by April 22nd. You can change your choice later, e.g., if you decide to work on an open problem, but you cannot make any progress, so you present a related prior work instead.

Suggested papers
  1. Alexandr Andoni, Negev Shekel Nosatzki. Edit Distance in Near-Linear Time: it’s a Constant Factor. FOCS 2020 
  2. Bartlomiej Dudek, Pawel Gawrychowski, Tatiana Starikovskaya. All non-trivial variants of 3-LDT are equivalent. STOC 2020
  3. Timothy M. Chan, Qizheng He. Reducing 3SUM to Convolution-3SUM. SOSA 2020 
  4. Kyriakos Axiotis, Christos Tzamos. Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms. ICALP 2019
  5. William Kuszmaul. Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation. ICALP 2019
  6. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. STOC 2018
  7. Karl Bringmann, Allan Grønlund, Kasper Green Larsen. A Dichotomy for Regular Expression Membership Testing. FOCS 2017
  8. Marvin Künnemann, Ramamohan Paturi, Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. ICALP 2017


Feb 25th: Logistics, introduction, quadratic kernel and bounded search tree algorithm for Vertex Cover, definitions of FPT and kernelization. Chapters 1 and 2.1 of the FPT book. Slides: logistics, introductionProblem set 1.

Mar 4th: Better branching and LP-based kernel for VC, color coding for Longest Path. Chapters 2.5, 3.1, 3.2, 5.2. Problem set 2. Notes.

Mar 11th: VC above LP, iterative compression, introduction to treewidth. Chapters 3.4, 4.2, 7.1, 7.2. Problem set 3. Notes.

Mar 18th: FVS in undirected graphs, computing treewidth, grid theorems, nice decomposition. Chapters 4.3, 7.6, 7.7. Problem set 4. Notes.

Mar 25th: Dominating Set parameterized by treewidth, Courcelle’s theorem, W[1]- and W[2]-hardness. Chapters 7.3.2, 7.4, 13. Problem set 5. Notes.

Apr 1st: ETH and SETH, lower bounds for FPT problems, Orthogonal Vectors, lower bound for diameter approximation. Chapter 14. Problem set 6. Notes. Further (optional) reading: IPZ’01, Williams’05, RVW’13.

Apr 8th: No class (Easter break).

Apr 15th: SETH-based lower bound for LCS, BMM-based lower bound for Approximate Pattern Matching. Problem set 7. Notes. Further (optional) reading: ABVW’15, BK’15, GU’18.

Apr 22nd: Problems equivalent to APSP: (min,+)-product, Negative Triangle, Radius, Max Submatrix. Problem set 8. Notes. Further (optional) reading: VWW’10, AGVW’15, BDT’16, LU’18.

Apr 29th: Students’ presentations. APSP in unweighted graphs: Seidel’s and Zwick’s algorithms. Problem set 9. Notes. Further (optional) reading: Seidel’95, Zwick’02.

May 6th: 3SUM, Convolution 3SUM, Jumbled Indexing. Problem set 10. Notes. Further (optional) reading: Pătrașcu’10, TCLL’14, KPP’16, CH’20.

May 13th: No class (Ascension Day). Optional: video.

May 20th: Zero Triangle, (min,+)-convolution. Problem set 11. Notes. Further (optional) reading: VW’13, VWW’13, CMWW’17, KPS’17, VWX’20.

May 27th: Distributed PCP framework, hardness of approximate Max Inner Product. Problem set 12. No notes available. Further (optional) reading: ARW’17, Rubinstein’18, Chen’18, RVW’19.

Jun 3rd: Students’ presentations.