Seminars

View all Seminars  |  Download ICal for this event

Improved (exponential time) algorithms: A case study for Subset Sum and Bin Packing

Series: Theory Seminar

Speaker: Dr. Jesper Nederl of Associate Professor Algorithms and Complexity group Utrecht University

Date/Time: Oct 01 16:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
Given an algorithm for a computational problem, a natural question is: Can its time or space efficiency be improved? We study this question for some natural and/or old algorithms for NP-complete problems.
<br>
Specifically, we survey some of the modern techniques to design such improved algorithms, with a focus on the Subset Sum and Bin Packing problems:
<br>
The algorithm by Schroeppel and Shamir (FOCS'79) solving Subset Sum on instances with n items in O(2^{n/2}) time and O(2^{n/4}) space can be improved to an algorithm using the same time and O(2^{0.249999n}) space. The trivial O(2^n) time and poly(n) space algorithm for Subset Sum can be improved to an O(2^{0.86n}) time poly(n) space algorithm, assuming random read-only access to random bits. The standard algorithm solving Bin Packing with n items in O(2^n) can be improved to an algorithm running in time O((2??ε_b)^n), where n denotes the number of items and ε_b is a positive number that only depends on the number of bins b available in the instance.
<br>
Two key modern techniques we will discuss are (1) a new method based on anti-concentration of subset sums (along with structural new insights in additive combinatorics) and (2) the representation method by Joux and Howgrave-Graham (EUROCRYPT'10) to navigate through the search space in an improved way,
<br>
<br>
We will discuss parts of the following works:
<br>
Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, Karol Wegrzycki: A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics. SODA 2021: 1682-1701.
<br>
Jesper Nederlof, Karol Wegrzycki: Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors. STOC 2021: 1670-1683
<br>
Nikhil Bansal, Shashwat Garg, Jesper Nederlof, Nikhil Vyas: Faster space-efficient algorithms for subset sum and k-sum. STOC 2017: 198-209
<br>
Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof: Dense Subset Sum May Be the Hardest. STACS 2016: 13:1-13:14
<br>
<br>
<br>
Microsoft Teams Link:
<br>
<a href="Link
<br>
<br>
For more details about the seminar please visit the website at Link

Host Faculty: Dr. Arindam Khan