A Fast Polynomial Space Algorithm for Subset Sum

1,954 views · Published 10 November 2016 · 1:02:08 · Indexed 30 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

I will describe an algorithm for the subset sum problem that runs in 2^{0.86n} time and uses polynomial  pace. 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 builds on  some recent work of Beame et al.    Based on joint work with Shashwat Garg, Jesper Nederlof and Nikhil Vyas

See more on this video at https://www.microsoft.com/en-us/research/video/fast-polynomial-space-algorithm-subset-sum/

More from this channel