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.
