Before revision:  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 \}| \leq 2^{(1-\varepsilon)n} for every v then |\{ w(X): X \subseteq \{1,\ldots,n\} \}|\leq 2^{\delta n}.
After revision:  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 \}| \leq 2^{(1-\varepsilon)n} for some v then |\{ w(X): X \subseteq \{1,\ldots,n\} \}|\leq 2^{\delta n}.