Fine-Grained Complexity Theory

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. We present a mix of upper and lower bounds for fundamental poynomial-time solvable problems, often by drawing interesting connections between seemingly unrelated problems. A prototypical result presented in this course is the following: If there is a substantially faster algorithm for computing all-pairs shortest paths in a weighted graph, then there also is a substantially faster algorithm for checking wether the graphs has a negative triangle (and vice versa). The techniques for proving such statements have been developed quite recently and most results taught in this course are less than five years old.

An important part of the course are the exercises, where you will design conditional lower bounds essentially on your own. There will be 6 exercise sheets and you need to collect at least 50% of all points on exercise sheets to be admitted to the exam. You are allowed to collaborate on the exercise sheets, but you have to write downa solution on your own, using your own words.Please indicate the names of your collaborators for each exercise you solve.Further, cite all external sources that you use (books, websites, research papers, etc.).

Lecture 01 (17 Oct)

• Overview (conditional lower bounds, central problems), machine model, NFA acceptance lower bound.
• Further Reading:  CT-PTP Slide 1

Lecture 02 (19 Oct)

• ETH, lower bounds for Dominating Set and q-Dominating Set.
• Further Reading: [Impagliazzo, Paturi '01], [Impagliazzo, Paturi, Zane '01], [Patrascu, Williams '10]

Lecture 03 (24 Oct)

• SETH, SETH-based lower bound for q-Dominating Set, OVH, OVH-based lower bound for Longest Common Subsequence
• Further Reading: CT-PTP Slide 2, [Impagliazzo, Paturi '01], [Bringmann,Künnemann'15], [Abboud,Backurs,Vassilevska-Williams'15]

Lecture 04 + 05 (02+07 Nov)

• Polynomial Method for OV
• Further Reading: [Abboud, Williams, Yu '15], CPTP-Slide 3

Lecture 06 (14 Nov)

• Quadratic algorithm for 3SUM, log-factor improvement, low-depth decision tree
• Further Reading: [Gronlund,Pettie'14], CPTP-Slide 6

Lecture 07 (16 Nov)

• finished log-factor improvement for 3SUM, 3SUM-hardness of geometric problems and Zero-Weight Triangle
• Further Reading: [Gajentaan,Overmars'95], [Vassilevska-Williams,Williams'09], CPTP-Slide 6, CPTP-Slide 7

Lecture 08 (21 Nov)

• equivalence of 3SUM and Conv-3SUM
• Further Reading: [Patrascu'10], [Kopelowitz,Pettie,Porat'16], CPTP-Slide 7

Lecture 09 (28 Nov)

• finished equivalence of Lecture 08: analysis of hash function
• definition of fine-grained reductions, subcubic equivalence of (min,+) product and APSP
• Further Reading: CPTP-Slide 5

Lecture 10 (30 Nov)

• subcubic equivalence of APSP, Negative (All-Pairs) Triangle, Radius
• Further Reading: [Vassilevska-Williams,Williams'10], CPTP-Slide 5

Lecture 11 (5 Dec)

• Subcubic Equivalence of APSP and MaxCenteredSubmatrix
• introduced (combinatorial) BMM hypothesis, combinatorial subcubic equivalence to (All-Pairs) Triangle
• Further Reading: [Backurs,Dikkala,Tzamos'16], [Vassilevska-Williams, Williams'10], CPTP-Slide 5. CPTP-Slide 8

Lecture 12 (12 Dec)

• BMM-based lower bound for Sliding Window Hamming Distance
• Minimum Node-weighted Triangle: BMM lower bound and faster algorithm using fast matrix multiplication
• Further Reading:  [Czumaj,Lingas'07], CPTP-Slide 8

Lecture 13 (14 Dec)

• Partial relations among SETH, 3SUM, APSP: Reduction from k-Clique to OV, non-tight reduction from k-SUM to k-OV

Lecture 14 (19 Dec)

• Partial relations among SETH, 3SUM, APSP: finished non-tight reduction from k-SUM to k-OV, k-SUM algorithm via polynomial multiplication, k-sum-free sets
• Further Reading: [Behrend'46]

Lecture 15 (02 Jan)

• Partial relations among SETH, 3SUM, APSP: Reduction from k-Clique to OV, non-tight reduction from k-SUM to k-OV

Lecture 16 (04 Jan)

• Nondeterministic SETH: introduced (co-)nondeterministic algorithms and verification algorithms, showed that 3-SUM is efficiently verifiable
• Further Reading: [CGIMPS'15]

Lecture 17 (09 Jan)

• Efficient Computation with Polynomials: Multipoint evaluation, interpolation, division with remainder
• Further Reading: lecture notes by M. Bläser and C. Saha on [division] and [multipoint evaluation and interpolation]

Lecture 18 (16 Jan)

• Randomized Nondeterministic SETH is false; arithmetic circuits and the Schwartz-Zippel lemma
• Further Reading: [Williams'16]

Lecture 19 (18 Jan)

• Hardness of Approximation in P: Assuming SETH, MaxInnerProduct has no 1.99-approximation in strongly subquadratic time
• Further Reading: [Abboud,Rubinstein,Williams'17]

Lecture 20 (23 Jan)

• (min,+)-convolution: relation to APSP and 3SUM, equivalence to (min,+)-violation

• Further Reading: [Cygan,Mucha,Węgrzycki,Włodarczyk'17], [Künnemann,Paturi,Schneider'17], [Bremner,Chan,Demaine,Erickson,Hurtado,Iacono,Langerman,Patrascu,Taslakian'14]

Lecture 21 (30 Jan)

• OV-based lower bound for dynamic #SSR, OMv conjecture, OMv-based lower bound for SSR

• Further Reading: [Abboud,Vassilevska-Williams'14], [Henzinger,Krinninger,Nanongkai,Saranurak'17]

Lecture 22 (1 Feb)

• recap + open problems