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:Faster Space Efficient Algorithms for Subset Sum and Knapsack
Speaker:Jesper Nederlof
coming from:Eindhoven University of Technology
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 31 January 2017
Duration:30 Minutes
Building:E1 4 - MPI-INF
We present a randomized Monte Carlo algorithm that solves a given instance of Subset Sum on n integers using O*(2^{0.86n}) time and O*(1) space, where O*() suppresses factors polynomial in the input size. The algorithm assumes random access to the random bits used. The same result can be obtained for Knapsack on n items, and the same methods also have consequences for the k-Sum problem. Joint work with Nikhil Bansal, Shashwat Garg and Nikhil Vyas.
Name(s):Holger Dell
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Holger Dell, 01/11/2017 07:04 PM
Last modified:
Uwe Brahm/MPII/DE, 01/31/2017 04:00 AM
  • Holger Dell, 01/11/2017 07:04 PM -- Created document.