Fine-Grained and Parameterized Complexity

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