BAD'16 Poster

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.


  The University of Bristol   EPSRC