The term fine-grained describes the new branch of complexity theory where computational lower bounds are based on hypothesis other than \(\text{P} \neq \text{NP}\). Originating from the objective to derive bounds for polynomial time solvable problems, surprisingly powerful conjectures about best running-times for some classical problems have emerged. For example, the assumption that the all-pairs-shortest path problem can not be solved in subcubic time (APSP conjecture) implies the same lower bound for several other problems. The probably most surprising result of this type shows that the APSP conjecture implies that there is no subcubic algorithm for the negative-triangle problem (decide if an edge-weighted graph contains a triangle with weights that sum up to a negative number).
In this course we will discuss four conjectures from fine-grained complexity: SETH, OV, 3SUM and APSP. We will learn the reduction techniques to show computational lower bounds based on such conjectures and give classifications for many fundamental poynomial-time solvable problems. Later in the lecture, we will also see where the conjectures and ideas of fine-grained complexity are useful from the perspective of approximation and parameterized algorithms.
The goals of this course are to provide an overview of the complexity landscape within P (as far as currently established), teach the reduction techniques for lower bounds under SETH, OV, 3SUM and APSP, and further give some insight into the current trends in fine-grained complexity.
