Selected Topics in FineGrained Complexity Theory
Seminar
Lecturers:  Karl Bringmann and Marvin Künnemann 

Time:  Tuesday, 4:15 PM (preliminary slot, up for discussion) 
Room:  024 in E1.4 (MPIIBuilding) 
First Meeting:  April 10, 2018 
Credits:  7 credit points 
Prerequisites:  This seminar aims at participants of the lectures Finegrained Complexity Theory (Winter 17/18) / Complexity Theory of PolynomialTime 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. 
Description
Complexity theory traditionally distinguishes whether a problem can be solved in polynomial time (by providing an efficient algorithm) or the problem is NPhard (by providing a reduction). For practical purposes however the label "polynomialtime" 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 finegrained view of the complexity of polynomialtime problems.
As a followup to the lecture "Finegrained 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
Topics
1  Lower bounds for sparse graphs  
"Tight Hardness for Shortest Cycles and Paths in Sparse Graphs"  A Lincoln, V. Vassilevska Williams, R. Williams  SODA'18 
2  Lower Bounds for Multivariate Algorithms  
"Multivariate FineGrained Complexity of Longest Common Subsequence"  K. Bringmann, M. Künnemann  SODA'18 
3  Lower Bounds for Problems on Compressed Strings  
A. Abboud, A. Backurs, K. Bringmann, M. Künnemann  FOCS'17  
4  OV Completeness  
"Completeness for FirstOrder Properties on Sparse Structures with Algorithmic Applications"  J. Gao, R. Impagliazzo, A. Kolokolova, R. Williams  SODA'17 
5  AverageCase FineGrained Complexity  
M. Ball, A. Rosen, M. Sabin, P. N. Vasudevan  STOC'17  
6  Complexity of String Similarity on Correlated Input  
"The Complexity of Problems in P Given Correlated Instances"  S. Goldwasser, D. Holden  ITCS'17 
7  Lower Bounds for OV in other computational models  
"The Orthogonal Vectors Conjecture for Branching Programs and Formulas"  D. Kane, R. Williams  unpublished (arXiv) 
8  Lower Bounds and Algorithms for Regular Expression Matching/Membership  
A. Backurs, P. Indyk  FOCS'16  
K. Bringmann, A. Grønlund, K. Green Larsen  FOCS'17  
9  Connections between Integer Programming and (min,+)/regular convolution  
K. Jansen, L. Rohwedder  unpublished (arXiv)  
10  Lower Bounds and Algorithms concerning kOPT and bitonic TSP  
"FineGrained Complexity Analysis of Two Classic TSP Variants"  M. de Berg, K. Buchin, B. M. P. Jansen, G. Woeginger  ICALP'16

11  Tight Upper and Lower Bounds on Pattern Matching with Mismatches  
P. Gawrychowski, P. Uznański  unpublished (arXiv)  
R. Clifford, A. Fontaine, E. Porat, B. Sach, T. Starikovskaya  SODA'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. Weimann  SODA'18 
13  Hardness for Integer OV  
R. Williams  SODA'18  
"On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product"  L. Chen  unpublished (arXiv) 
14  Further developments in Hardness of Approximation in P  
"On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product"  L. Chen  unpublished (arXiv) 
"On the Parameterized Complexity of Approximating Dominating Set"  Karthik C. S., B. Laekhanukit, P. Manurangsi  STOC'18 
"Hardness of Approximate Nearest Neighbor Search"  A. Rubinstein  STOC'18 
Schedule
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 