A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

In the Bin Packing problem one is given n items with different weights
and m bins with a given capacity; the goal is to distribute the items
over the bins without exceeding the capacity.
Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an O(2^n) time
algorithm for Bin Packing.
In this paper we show that for every m there exists a constant s_m > 0
such that an instance of Bin Packing with m bins can be solved in
O((2-s_m)^n) time.
Before our work, such improved algorithms were not known even for m
equals 4.
A key step in our approach is a new result in Littlewood-Offord theory
on the additive combinatorics of subset sums.
(joint work with Jesper Nederlof, Jakub Pawlewicz Karol Węgrzycki that
will appear at SODA'21)