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

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ü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

ITCS'17

 

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

FOCS'16

"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

ICALP'16

 

 

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

STOC'18

"Hardness of Approximate Nearest Neighbor Search"A. RubinsteinSTOC'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 Room changed to HS 001! Lower Bounds and Algorithms concerning k-OPT and bitonic TSP
19 Jun Anna 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