Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
Speaker:Karl Bringmann
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 2 October 2018
Duration:30 Minutes
Building:E1 4
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.

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Karl Bringmann, 10/01/2018 03:27 PM
Last modified:
Uwe Brahm/MPII/DE, 10/02/2018 07:01 AM
  • Karl Bringmann, 10/01/2018 03:27 PM -- Created document.