Nikhil Bansal: A fast polynomial space algorithm for Subset Sum

Speaker: Nikhil Bansal

Date: Tuesday, March 07, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: Patil/Kiva G449

Event Type:

Room Description:

Host: Aleksander Madry

Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Nikhil Bansal: A fast polynomial space algorithm for Subset Sum

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

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Deborah Goodwin at Tuesday, February 21, 2017 at 3:28 PM.