Selected Topics in Fine-Grained Complexity Theory


Lecturers:Karl Bringmann and Marvin Künnemann
Time:Tuesday, 4:15 PM (preliminary slot, up for discussion)
Room:024 in E1.4 (MPII-Building)
First Meeting:April 10, 2018
Credits:7 credit points

This seminar aims at participants of the lectures Fine-grained Complexity Theory (Winter 17/18) / Complexity Theory of Polynomial-Time Problems (Summer 16). We will deepen our understanding of the field by reading and presenting recent works on the subject.

You may also participate in this seminar if you have not attended any of the above lectures - in this case, you should bring a strong background in complexity theory and algorithms.


Complexity theory traditionally distinguishes whether a problem can be solved in polynomial time (by providing an efficient algorithm) or the problem is NP-hard (by providing a reduction). For practical purposes however the label "polynomial-time" is too coarse: it may make a huge difference whether an algorithm runs in say linear, quadratic, or cubic time. In this course we explore an emerging subfield at the intersection of complexity theory and algorithm design which aims at a more fine-grained view of the complexity of polynomial-time problems.

As a follow-up to the lecture "Fine-grained complexity theory", we discuss recent works that have appeared in this field, exploring both depth and breadth of current developments.

To collect credits for the course, you will give a presentation about a topic chosen from the list below - we will give a brief overview over these results in the first meeting of the course.

List of assigned topics

  • Lower Bound for Tree Edit Distance: André
  • Lower Bounds for OV in other computational models: Bhaskar


1 - Lower bounds for sparse graphs

"Tight Hardness for Shortest Cycles and Paths in Sparse Graphs"

A Lincoln,  V. Vassilevska Williams,  R. Williams



2 - Lower Bounds for Multivariate Algorithms

"Multivariate Fine-Grained Complexity of Longest Common Subsequence"

K. Bringmann, M. KünnemannSODA'18


3 - Lower Bounds for Problems on Compressed Strings

"Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve"

A. Abboud, A. Backurs, K. Bringmann, M. KünnemannFOCS'17


4 - OV Completeness

"Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications"

J. Gao, R. Impagliazzo, A. Kolokolova, R. WilliamsSODA'17


5 - Average-Case Fine-Grained Complexity

"Average-Case Fine-Grained Hardness"

M. Ball,  A. Rosen,  M. Sabin,  P. N. VasudevanSTOC'17


6 - Complexity of String Similarity on Correlated Input

"The Complexity of Problems in P Given Correlated Instances"

S. Goldwasser, D. Holden



7 - Lower Bounds for OV in other computational models

"The Orthogonal Vectors Conjecture for Branching Programs and Formulas"

D. Kane, R. Williamsunpublished (arXiv)


8 - Lower Bounds and Algorithms for Regular Expression Matching/Membership

"Which Regular Expression Patterns are Hard to Match?"

A. Backurs, P. Indyk


"A Dichotomy for Regular Expression Membership Testing"

K. Bringmann, A. Grønlund, K. Green LarsenFOCS'17


9 - Connections between Integer Programming and (min,+)/regular convolution

"On Integer programming and Convolution"

K. Jansen, L. Rohwedder

unpublished (arXiv)


10 - Lower Bounds and Algorithms concerning k-OPT and bitonic TSP

"Fine-Grained Complexity Analysis of Two Classic TSP Variants"

M. de Berg, K. Buchin, B. M. P. Jansen, G. Woeginger




11 - Tight Upper and Lower Bounds on Pattern Matching with Mismatches

"Optimal trade-offs for pattern matching with k mismatches"

P. Gawrychowski, P. Uznańskiunpublished (arXiv)

"The k-mismatch problem revisited"

R. Clifford, A. Fontaine, E. Porat, B. Sach, T. StarikovskayaSODA'16


12 - Lower Bound for Tree Edit Distance

"Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)"

K. Bringmann, P. Gawrychowski, S. Mozes, O. WeimannSODA'18


13 - Hardness for Integer OV

"On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry"

R. WilliamsSODA'18

"On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product"

L. Chenunpublished (arXiv)


14 - Further developments in Hardness of Approximation in P

"On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product"

L. Chenunpublished (arXiv)
"On the Parameterized Complexity of Approximating Dominating Set"Karthik C. S., B. Laekhanukit, P. Manurangsi


"Hardness of Approximate Nearest Neighbor Search"A. RubinsteinSTOC'18


Date Speaker Topic
10 Apr KB+MK Introduction, Overview of Topics, Assignment of Topics
17 Apr André Nusser Lower Bound for Tree Edit Distance
24 Apr (Room not available)
01 May Canceled (Holiday)
08 May  
15 May  
22 May  
29 May  
05 Jun  
12 Jun  
19 Jun  
26 Jun  
03 Jul  
10 Jul  
17 Jul