Computer Science/Discrete Mathematics Seminar II
Hardness of Easy Problems and Fine-Grained Complexity
In recent years, a new “fine-grained” theory of computational hardness has been developed, based on “fine-grained reductions” that focus on exact running times for problems.
We follow the fashion of NP-hardness in a more delicate manner. We identify key problems for which we have a time t(n) solution, but believe that there is no $t(n)^{(1-eps)}$ solution for any eps>0. Then, we reduce the key problems in a fine-grained way to many important problems. Thus, getting a tight conditional lower-bounds for them.
This approach has led to the discovery of many meaningful relationships between problems, and to equivalence classes. One such key conjecture is a quantitative strengthening of the P!=NP conjecture called SETH.
Research on SETH-based lower bounds has flourished in particular in recent years. Showing, for example, that the classical algorithms are likely optimal for problems such as Diameter, Sub-tree Isomorphism, Edit Distance and Longest Common Subsequence.
In the first half of the seminar we will introduce and survey the classic conjectures and tools of these fine-grained reductions.
In the second half of it we will cover a recent technique (joint work with Abboud, Bringmann and Khoury) that translates many of these conditional-lower bounds to hold also for approximation algorithms. For example, we show that no distance oracle with O(1)-approximation, $m^{(1+o(1))}$ preprocessing time and $m^{o(1)}$ query time is likely to exist.