Selected Topics in Fine-Grained Complexity Theory
Seminar
| Lecturers: | Karl Bringmann and Marvin Künnemann |
|---|---|
| Time: | Tuesday, 4:15 PM |
| Room: | 024 in E1.4 (MPII-Building) |
| First Meeting: | April 10, 2018 |
| Credits: | 7 credit points |
| Prerequisites: | 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. |
News
- Room change: On June 12 we will be in HS 001, building E 1 3
- Talk on June 19 is canceled
Description
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.
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 Fine-Grained 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 First-Order Properties on Sparse Structures with Algorithmic Applications" | J. Gao, R. Impagliazzo, A. Kolokolova, R. Williams | SODA'17 |
5 - Average-Case Fine-Grained 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 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 | 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 | Bhaskar Ray Chaudhury | Lower Bounds for OV in other computational models |
| 15 May | (No talk) | |
| 22 May | Marvin Künnemann | Further developments in Hardness of Approximation in P |
| 29 May | Nick | OV Completeness |
| 05 Jun | (No talk) | |
| 12 Jun | Philipp | Lower Bounds and Algorithms concerning k-OPT and bitonic TSP |
| 19 Jun | Anna | Canceled! Connections between Integer Programming and (min,+)/regular convolution |
| 26 Jun | ||
| 03 Jul | Marian | Lower Bounds for Problems on Compressed Strings |
| 10 Jul | ||
| 17 Jul | Jannik | Complexity of String Similarity on Correlated Input |