N&O Lecture Jesper Nederlof (TU/e): Faster Space Efficient Algorithms for Subset Sum and Knapsack

Everyone is welcome to attend the public lecture of Jesper Nederlof. Abstract: Faster Space Efficient Algorithms for Subset Sum and KnapsackWe 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.
  • What Networks & Optimization
  • When Feb 08, 2017 from 10:00 AM to 11:00 AM (Europe/Amsterdam / UTC100)
  • Where Room L016 - CWI
  • Web Visit external website
  • Add event to calendar iCal

Everyone is welcome to attend the public lecture of Jesper Nederlof. Abstract:

Faster Space Efficient Algorithms for Subset Sum and Knapsack
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.