How to Prove Lower Bounds from the Strong Exponential Time Hypothesis

Perspective graduate students are encouraged to come, and the new time is meant to accommodate them.
The Strong Exponential Time Hypothesis (SETH) states that CNF-SAT (the satisfiability problem on n-variable k-CNF formulae when k is
unbounded) requires at least 2^{(1-o(1)) n} time. Assuming that SETH is true, it is possible to obtain numerous lower bounds on other problems of interest, including problems known to be solvable in polynomial time! In this talk I'll survey a couple lower bounds conditioned on SETH.

— Given an undirected, unweighted graph G=(V,E), it is easy to compute a 2-approximation of its diameter in linear time. Assuming SETH, any (3/2-eps)-approximation must take time O(|E|^{2-o(1)}).

— The Frechet distance is a measure of similarly between pairs of polygonal curves with length n. It is trivial to compute the discrete Frechet distance in O(n^2) time. Assuming SETH, no O(n^{2-eps}) time algorithm exists.

This talk covers material from
K. Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails, FOCS 2014, and L. Roditty and V. V. Williams. Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs, STOC 2013.