Nikhil Bansal: A fast polynomial space algorithm for Subset Sum
Tuesday, March 7, 2017 - 4:00pm to 5:00pm
Refreshments:
Light Refreshments at 3:50pm
Location:
Patil/Kiva G449
Speaker:
Nikhil Bansal
Seminar group:
Abstract: I will describe an algorithm for the subset sum problem that
runs in 2^{0.86n} time and uses polynomial space. Previously, all
algorithms with running time less than 2^n used exponential space, and
obtaining such a guarantee was open. Our algorithm is based on Floyd's
space efficient technique for cycle finding and some additive
combinatorics of subset sums.
Based on joint work with Shashwat Garg, Jesper Nederlof and Nikhil Vyas