  For $S \subseteq \{0,1\}^n$ a Boolean function $f \colon S \to \{-1,1\}$ is a
polynomial threshold function (PTF) of degree $d$ and weight $W$ if there is a
polynomial $p$ with integer coefficients of degree $d$ and with sum of absolute
coefficients $W$ such that $f(x) = \text{sign}(p(x))$ for all $x \in S$. We
study a representation of decision lists as PTFs over Boolean cubes $\{0,1\}^n$
and over Hamming balls $\{0,1\}^{n}_{\leq k}$.
  As our first result, we show that for all $d = O\left( \left( \frac{n}{\log
n}\right)^{1/3}\right)$ any decision list over $\{0,1\}^n$ can be represented
by a PTF of degree $d$ and weight $2^{O(n/d^2)}$. This improves the result by
Klivans and Servedio [Klivans, Servedio, 2006] by a $\log^2 d$ factor in the
exponent of the weight. Our bound is tight for all $d = O\left( \left(
\frac{n}{\log n}\right)^{1/3}\right)$ due to the matching lower bound by Beigel
[Beigel, 1994].
  For decision lists over a Hamming ball $\{0,1\}^n_{\leq k}$ we show that the
upper bound on weight above can be drastically improved to $n^{O(\sqrt{k})}$
for $d = \Theta(\sqrt{k})$. We also show that similar improvement is not
possible for smaller degrees by proving the lower bound $W = 2^{\Omega(n/d^2)}$
for all $d = O(\sqrt{k})$. \end{abstract}
