Campus Event Calendar
Event Entry
What and Who
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
Karl Bringmann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 2 October 2018
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Subset Sum on n input numbers and target t can be solved in time O(nt) by Bellman's 1962 dynamic programming algorithm, and since recently in near-linear time in n+t by a randomized algorithm. Here we provide a matching conditional lower bound under the Strong Exponential Time Hypothesis, ruling out algorithms in time t^{1−ε}·2^{o(n)} for any ε>0.
As a corollary, we prove a “Direct-OR” theorem for Subset Sum under the Strong Exponential Time Hypothesis, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of q given instances of Subset Sum is a YES-instance requires time (qt)^{1−o(1)}. As an application, we prove a conditional lower bound for the classic Bicriteria s,t-Path problem, separating it from Subset Sum.
Contact
Karl Bringmann
--email hidden
passcode not visible
logged in users only
Karl Bringmann, 10/01/2018 15:27 -- Created document.