BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20211001T120000Z
UID:c3193587405e85a5d199b2c2bde43d0f-202
DTSTAMP:19700101T120016Z
DESCRIPTION:Improved (exponential time) algorithms: A case study for Subset Sum and Bin Packing
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/202/improved-exponential-time-algorithms-a-case-study-for-subset-sum-and-bin-packing/
SUMMARY: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="https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d">https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
<br>
 <br>
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
DTSTART:20211001T120000Z
END:VEVENT
END:VCALENDAR