Algorithmic Uses of SETH-Based Lower Bounds

Despite the recent success of conditional lower bounds, sometimes the objection is voiced that such lower bounds are only as useful as the underlying hypotheses are justified. Researchers disbelieving in the Strong Exponential Time Hypothesis (SETH) might feel that lower bounds conditional on SETH are irrelevant to them. However, fine-grained reductions yield much more insights and have surprising uses. One particularly interesting example is the reoccurring phenomenon: Conditional lower bounds can inspire algorithmic improvements. In this talk we will discuss and illustrate this phenomenon, and as a case in point show how to obtain a faster algorithm for approximating the Fréchet distance on realistic curves by examining why the SETH-based lower bound of [Bringmann, FOCS'14] could not be strengthened.