  In the Bin Packing problem one is given $n$ items with weights
$w_1,\ldots,w_n$ and $m$ bins with capacities $c_1,\ldots,c_m$. The goal is to
find a partition of the items into sets $S_1,\ldots,S_m$ such that $w(S_j) \leq
c_j$ for every bin $j$, where $w(X)$ denotes $\sum_{i \in X}w_i$. Bj\"orklund,
Husfeldt and Koivisto (SICOMP 2009) presented an $\mathcal{O}^\star(2^n)$ time
algorithm for Bin Packing. In this paper, we show that for every $m \in
\mathbf{N}$ there exists a constant $\sigma_m >0$ such that an instance of Bin
Packing with $m$ bins can be solved in $\mathcal{O}(2^{(1-\sigma_m)n})$
randomized time. Before our work, such improved algorithms were not known even
for $m$ equals $4$. A key step in our approach is the following new result in
Littlewood-Offord theory on the additive combinatorics of subset sums: For
every $\delta >0$ there exists an $\varepsilon >0$ such that if $|\{ X\subseteq
\{1,\ldots,n \} : w(X)=v \}| \geq 2^{(1-\varepsilon)n}$ for some $v$ then $|\{
w(X): X \subseteq \{1,\ldots,n\} \}|\leq 2^{\delta n}$.
