

Bristol Algorithms Days 2016 Workshop on Efficient Algorithms and Lower Bounds
2  3 February 2016

Conditional Lower Bounds for Dynamic Programming Problems
Karl Bringmann
Assuming a lower bound on the time complexity of satisfiability (e.g.
the Strong Exponential Time Hypothesis), by designing a reduction from
satisfiability to any other problem such as longest common subsequence,
we can transfer the hardness of satisfiability and thus prove a
"conditional lower bound" for the time complexity of longest common
subsequence. We will discuss recent conditional lower bounds for dynamic
programming type problems such as longest common subsequence, edit
distance, or Fréchet distance, and others.
Back
 