BARC/EADS Talk by Karl Bringmann – Københavns Universitet

BARC/EADS Talk by Karl Bringmann


SETH-Based Lower Bounds for Subset Sum and Bicriteria Path


Bellman's 1962 pseudo-polynomial O(nT)-time algorithm for Subset Sum on n numbers and target T is taught in many undergraduate courses as an example for dynamic programming. We will briefly discuss a faster Õ(n+T)-time algorithm that I recently found. Then we will see a matching lower bound: Subset Sum cannot be solved in time T^{1−ε} 2^{o(n)} for any ε>0, unless the Strong Exponential Time Hypothesis (SETH) fails. Previously, such a lower bound was only known under the (much less standard) Set Cover hypothesis.

As a corollary, we prove a "Direct-OR" theorem for Subset Sum: Deciding whether one out of N given instances of Subset-Sum is a YES instance requires time (NT)^{1−o(1)} under SETH. It seems impossible to obtain this from the previous Set-Cover-based lower bound.

As an application of this corollary, we prove a tight SETH-based lower bound for the Bicriteria s,t-Path problem: On graphs with m edges and edge lengths bounded by L, we show that the O(Lm) pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to Õ(L+m), thus separating the problem from Subset Sum.


Karl Bringmann is a senior researcher at Max Planck Institute for Informatics. He is  interested in theoretical computer science in general. More specifically, he studys conditional lower bounds (e.g. based on the Strong Exponential Time Hypothesis) and algorithm design working mostly on strings and computational geometry. Previously, I stayed one year at ETH Zurich and four months at the Simons Institute for the Theory of Computing, Berkeley.