Karl Bringmann, ETH Zürich

15:30 - 16:00 Lehrprobe: k-Median Problem

16:00 - 16:45 Conditional Lower Bounds - A Surrogate for NP-hardness on Polynomial Time Problems

Abstract:

Suppose we have to solve a computational problem, say to compute the longest common subsequence of two strings. We have found a quadratic time algorithm, but our problem instances are so large that quadratic time is too slow. Should we keep searching for a faster algorithm?

Conditional lower bounds provide a way to prove barriers for polynomial time problems. We discuss several results obtained in this area in the last years, e.g., that computing the longest common subsequence of two strings takes quadratic time (assuming the so-called Strong Exponential Time Hypothesis). This yields strong evidence that we can stop searching for faster algorithms for these problems.

Just as NP-hardness results motivate approximation algorithms and fixed parameter tractability, a conditional lower bound for a polynomial time problem motivates to study relaxed variants of the problem.

Specifically, we may (1) study near-linear time approximation algorithms and (2) analyze the running time of algorithms depending on further input parameters. We discuss examples of both lines of research.