"A fast polynomial space algorithm for Subset Sum"
Nikhil Bansal (TU Eindhoven)
Monday, November 6, 2017, 2:00 pm
EBU3B, Room 4258
Abstract: I will describe an algorithm for the subset sum problem that runs in 2^{0.86n} time and uses polynomial space, assuming read-only random access to exponentially many random bits. 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